문제

양의 정수와 양의 정수 목표의 배열이 주어지면,
합이 대상보다 크거나 같은 부분 배열의 최소 길이를 반환합니다.
이러한 하위 배열이 없으면 대신 0을 반환합니다.

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: [4,3] 부분 배열의 합이 7이면서 최소 길이이다.

구현 전 예상 풀이

1. 모든 부분 배열을 구한다.
2. 부분 배열의 합이 타겟보다 크면서 최소 길이를 구한다.

모든 부분의 배열을 구하는 방법은 재귀를 이용해서 구할 수 있다.

Combination(int i, Stack stack){

	if (idx == nums.length) 
		sum = stack.sum();
		length = stack.size();

		if (sum >= target) 
			result = Min(result, length);
		
		return;
	

	num = nums[idx];

	subArray(idx + 1, stack);

	stack.push(num);
	subArray(idx + 1, stack);
	stack.pop();

}

구현 코드

통과 실패

class Solution {
    int[] nums;
    int target;
    int result = Integer.MAX_VALUE;
    public int minSubArrayLen(int target, int[] nums) {
        this.nums = nums;
        this.target = target;
        subArray(0, new Stack<>());

        if (result == Integer.MAX_VALUE) {
            return 0;
        }

        return result;
    }

    private void subArray(int idx, Stack<Integer> stack) {
        if (idx == nums.length) {
            int sum = 0;
            int length = stack.size();

            for (Integer integer : stack) {
                sum += integer;
            }

            if (sum >= target) {
                result = Math.min(result, length);
            }
            return;
        }

        int num = nums[idx];

        subArray(idx + 1, stack);

        stack.push(num);
        subArray(idx + 1, stack);
        stack.pop();
    }
}

위 방식으로 테스트케이스를 통과하지 못했다.
아무래도 부분 배열이 연속된 부분 배열을 뜻하는 것 같아서 다시 풀어보겠다.

1. 타겟보다 합이 적으면 오른쪽 숫자를 더한다.
2. 타겟보다 합이 커졌을때의 길이를 기록 후 왼쪽의 숫자를 합에서 뺀다.

1번과 2번을 반복하여 타겟보다 합이 클때 최소 길이를 구한다.

성공

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            int num = nums[right];
            sum += num;

            while (sum >= target && left <= right) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        if (minLength == Integer.MAX_VALUE) {
            return 0;
        }

        return minLength;
    }
}

209. Minimum Size Subarray Sum