[LeetCode] 209번: Minimum Size Subarray Sum

문제 링크: https://leetcode.com/problems/minimum-size-subarray-sum/

Minimum Size Subarray Sum - LeetCode

 

투 포인터는 빠삭하게 공부해야 할 알고리즘 중 하나이다.

한동안 관련 문제들 많이 풀었었는데 요즘 또 소홀해졌다.

 

이 문제의 경우 주어진 배열의 값이 모두 양의 정수이기 때문에

포인터 start와 end 모두 0부터 시작하여 누적합이 target s값 이상이 될 때까지 end를 증가시켜주면서 진행된다.

만약 누적합이 target s보다 커진 경우에는 start가 가리키는 값을 누적합에서 빼준 뒤 start값을 1 증가시켜줘야 한다.

이를 반복하여 start와 end 사이의 길이가 가장 작은 값을 찾으면 답을 구할 수 있다.

 

class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		if (nums.size() == 0) return 0;
		int s = 0, e = 0, sum = nums[0], min = nums.size(); bool found = false;
		for (; s <= e && e < nums.size();) {
			
			if (sum < target) {
				e++;
				if(e<nums.size())
					sum += nums[e];
			}
			else if (sum >= target) {
				if (min >= (e - s + 1)) {
					min = e - s + 1;
					found = true;
				}
				if (sum > target) {
					sum -= nums[s++];
				}
				else {
					e++;
					if (e < nums.size())
						sum += nums[e];
				}
			}
		}
		
		if(found)
			return min;
		return 0;
	}
};