문제

자연수로 이루어진 nums 배열에서 합이 target 이상인 subarray 중 가장 짧은 길이를 리턴하는 문제이다.

$O(n)$ 풀이

시작 인덱스(left)와 끝 인덱스(right) 사이의 모든 원소의 합(sum)을 관리하는 방법으로 sliding window으로 풀이하였다. left가 증가하면 sum이 감소하며 right가 증가하면 sum이 증가한다.

sum이 target 이상이면 answer 값을 업데이트하며 길이가 최소인 것을 찾아야하기 때문에 현재 left에 해당하는 원소 값을 sum에서 빼주고 left를 증가시킨다.

반대로 sum이 target 미만이면 sum을 증가시켜주기 위해 right를 증가시키는데 만약 right가 nums.length - 1 값이라면 반복문을 탈출한다. right가 끝에 도달해 right를 증가시키지 못하며 sum 또한 증가시키지 못하기 때문에 sum이 target 이상인 경우를 찾을 수 없기 때문이다.

left = 0, right = 0, sum = nums[0]
while
  if sum >= target then
	answer = min(answer, right - left + 1)
	sum -= nums[left++]
  else
	if right == numns.length - 1 then break
	else sum += nums[++right]

이 방법은 시간복잡도 $O(n)$이며 공간복잡도는 $O(1)$이다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
		int left = 0, right = 0;
		int sum = nums[0];
		int answer = Integer.MAX_VALUE;
		while(true) {
			if (sum >= target) {
				answer = Math.min(answer, right - left + 1);
				sum -= nums[left++];
			} else {
				if (right == nums.length - 1) {
					break;
				} else {
					sum += nums[++right];
				}
			}
		}

		return answer == Integer.MAX_VALUE ? 0 : answer;
	}
}

$O(n log n)$ 풀이

시간복잡도에 $O(logn)$이 들어가면 보통 분할하는 방법이 쓰이는거라 감으로 이진탐색이 쓰이는 것같았지만 풀이를 생각하지는 못했다. Solution에서 $O(nlogn)$ 풀이를 찾아봤지만 완전히 이해하지 못해 다시 풀어봐야할 것같다.