Leetcode - Minimum Size Subarray Sum

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Approach

EN

KR

타겟 값과 일치하거나 큰 값을 가진 원소의 제일 짧은 배열의 길이를 찾아야 하므로 전체 배열 길이의 원소들의 합에서 오른쪽을 한칸 씩 줄여서 나온 길이와 왼쪽을 한칸 씩 줄여서 나온 길이를 비교해 더 짧은 쪽을 리턴한다가 내가 생각한 최선의 방법이었다. 슬라이딩 윈도우의 경우 아직 개념의 이해가 잘 가지 않아 그냥 코드를 따라치긴 싫었다. (윈도우의 초기 크기 설정을 어떻게 잡아야할지 모르겠다.)

하지만 내 방법의 문제는 [5,1,3,5,10,7,4,9,2,8] 과 같은 가운데 원소배열의 합이 제일 짧을 때. 나는 무조건 왼쪽과 오른쪽으로 이동했으므로 해당 방법이 통하지 않았다.

code

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let rightCnt = 0;
    let leftCnt = nums.length;
    let sum = 0;

    for (const n of nums) {
        sum += n;
    }

    if (sum < target) {
        return 0;
    }

    let rightSum = sum;
    let leftSum = sum;
    let leftMin = 0;
    let rightMin = 0; 

    for (let i=nums.length-1; i>= 0; i--) {
        rightSum -= nums[i];
        if (rightSum >= target) {
            rightCnt++;
        }else {
            rightMin = nums.length-rightCnt;
            break;
        }
    }

    for (let i=0; i<nums.length; i++) {
        leftSum -= nums[i];
        if (leftSum >= target) {
            leftCnt--;
        }else {
            leftMin = nums.length-i;
            break;
        }
    }

    console.log(rightMin);
    console.log(leftMin);


    if (leftMin < rightMin) {
        return leftMin;
    }else {
        return rightMin;
    }

    // 가운데가 최소배열일 때 문제가 발생
};

Review

접근방법은 비슷하다면 비슷하고 다르다면 완전히 달랐다 하하 배열의 최소길이는 Infinity 라는 무한대를 줘야했다.

일단 배열의 첫번째 인덱스부터 오른쪽으로 확장시키면서 sum에 더한 뒤 sum이 타겟보다 크거나 같다면 최소길이를 다시 재고, Math.min을 이용하여 기존 최소길이와 현재 최소길이 중 더 작은 값을 대입한다.

그리고 배열을 맨 왼쪽원소부터 하나씩 제거해 나간다. (단, sum이 target보다 크거나 같다는 하에)

마지막으로, 만약 배열 최소길이가 무한대가 아니라면(초기값) 현재 최소길이를 리턴, 무한대라면 0을 리턴한다.

code

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
function minSubArrayLen(target, nums) {
    let left = 0; // 윈도우의 왼쪽 경계
    let sum = 0; // 현재 윈도우의 합
    let minLength = Infinity; // 최소길이는 무한한 길이부터 시작

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right]; // 윈도우를 오른쪽으로 확장

        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1); // 최소 길이 업데이트
            sum -= nums[left]; // 윈도우를 왼쪽으로 축소
            left++;
        }
    }

    return minLength !== Infinity ? minLength : 0;
}