[LeetCode] 209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum

개요

1. 양수 배열 nums가 주어진다.
2. 요소 합이 target 이상인 subArray의 최소 사이즈를 찾아라

문제 해결 아이디어

• 특정 조건을 만족하는 배열의 구간 (subArray) 을 찾아야 한다.
  • 연속적인 데이터의 하위 집합을 찾아야 함
• 구간의 크기가 최소가 되도록 해야 한다.
  • 구간의 크기가 가변적인 경우

🧐 슬라이딩 윈도우를 활용하자

의사 코드

1. 왼쪽 인덱스와 오른쪽 인덱스를 가르키는 포인터를 선언한다.
2. sum 변수에 오른쪽 인덱스의 값을 더한다.
3. sum 이 target보다 크거나 같다. (while)
   3-1. sum 에서 왼쪽 인덱스의 값을 뺀다.
   3-2. (왼쪽 인덱스 : 오른쪽 인덱스) 구간의 길이를 구한다.
   3-3. (왼쪽 인덱스 : 오른쪽 인덱스) 구간의 길이가 min 보다 작다. (조건)
   3-3-1. min값을 업데이트 한다.
   3-4. 왼쪽 인덱스를 하나 증가시킨다.
4. 오른쪽 인덱스를 하나 증가시킨다.

left = 0
right = 0
while(right < 배열길이){
	합 = 합 + 배열[right]
    while(합 >= target){
    	합 = 합 - 배열[left]
        if([left:right] 길이가 최소) min = right - left + 1
        left++
    }
    right++
}

결과

전체 코드 github 링크

다른 풀이

public int minSubArrayLen(int target, int[] nums) {
        int i=0;
        int j=0;
        int min=Integer.MAX_VALUE;
        int sum=0;
        while(j<nums.length){
            sum+=nums[j];
            if(sum>=target){
                while(sum>=target){
                    min=Math.min(min,j-i+1);
                    sum-=nums[i];
                    i++;
                }
            }
            j++;
        }
        if(min==Integer.MAX_VALUE)
            return 0;
        else
            return min;
    }

사실 이 문제는 내가 풀지 못했다.
그래서 설명이 가장 잘 나와있는 솔루션을 가져왔다.
슬라이딩 윈도우 방식에 대한 이해를 잘 못하고 있었고, 그것을 구현하는 것도 익숙하지 않아서 고전했던 것 같다.
그래도 블로그를 작성하며, 이 방식을 많이 이해한 것 같아 기쁘다.
이 풀이에서 일정 구간의 sum이 target을 넘으면 왼쪽 인덱스부터 차례로 빼며, 최소 구간 길이를 구하는데 이런 사고법을 꼭 기억해두어야겠다.