[C] LeetCode 209. Minimum Size Subarray Sum

문제(원문)

 

문제(번역)

양수가 담긴 배열 nums와 양의 정수 target이 주어진다.

이때 subarray의 합이 target보다 크거나 같은 subarray의 최소 길이를 반환해라.

적절한 subarray가 존재하지 않는다면 대신 0을 반환해라. 

접근 방법

처음에는 감이 잡히지 않아 해당 문제의 주제를 보니 슬라이딩 윈도우가 있다.

슬라이딩 윈도우란 배열이나 문자열에서 연속된 구간을 잡아두고, 그 구간을 한칸씩 밀면서 원하는 조건을 찾는 기법이라고 한다.

 

현재 구간의 합이 target보다 작으면 오른쪽으로 한칸을 늘린다.

만약 현재 구간의 합이 target 보다 크거나 같다면 최소 길이인지 확인 후 갱신한다. 그리고 target보다 작아질때까지 구간을 왼쪽에서 한칸 당겨서 줄여본다. 그리고 다시 조건을 만족하는 최소 길이인지 검사한다.

 

만약 단 한번도 갱신된적이 없으면 0을 반환하고, 아니라면 구했던 최소 길이를 반환하도록 코드를 작성했다.

 

소스 코드

int minSubArrayLen(int target, int* nums, int numsSize) {
    int curSum=0, minSize = numsSize+1, left = 0, right= 0;
    for(right = 0 ; right < numsSize ; right++) {
        curSum += nums[right]; 
        while(curSum >= target) {
            minSize = (minSize > right-left+1) ? right-left+1 : minSize;
            curSum -= nums[left++];
        }
    }
    return (minSize == numsSize+1) ? 0 : minSize;
}