Minimum Size Subarray Sum

---

💬 문제

[문제 링크]

양의 정수 배열 nums
합이 target 이상이 되는 부분배열 중
원소 개수가 가장 적은 배열 길이 반환
없을 경우 0 반환

✍️ 나의 풀이

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

    for (let i = 0; i <= nums.length; i++) {
        if (sum < target) {
            sum += nums[i];
            cnt++;
        } else {
            res = cnt < res ? cnt : res;
            sum -= nums[i - cnt];
            cnt--;
            i--;
        }
    }

    return res === nums.length + 1 ? 0 : res;
};

res는 가장 작은 부분 배열의 길이를 저장할 용도
끝까지 바뀌지 않은 경우 부분 배열이 없으므로 0 반환
nums를 순회하면서 각 인덱스 값을 더하고 (sum)
더해진 원소 개수를 cnt에 저장
sum이 target 이상이 되었을 경우
지금까지의 cnt와 res를 비교하여 작은 것으로 교체하고
다음 경우의 수 계산을 위해 처음 더했던 인덱스를 제외한 뒤 확인

📌 결과

Accepted
Runtime 52ms (Beats 90.09%)
Memory 53.19MB (Beats 57.60%)

📚 러닝 포인트

설명에서 O(n)으로 구할 수 있다는 걸 보고 중첩 반복문을 안 쓰기 위해서 노력했다. 처음에는 다음 경우의 수 계산을 위해 지금까지 더한 것에서 가장 앞에 있는 인덱스 값을 빼는 방법이 아니라, 합을 시작했던 인덱스 다음 부터 다시 하나씩 더하는 방법을 썼었다.

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum >= target) {
            let len = i - start + 1;
            res = len < res ? len : res;
            i = start;
            start++;
            sum = 0;
        }
    }

그랬더니 런타임이 무려 2389ms가 나왔다. 무언가 잘못되었단 걸 깨닫고 런타임 결과가 상위인 코드들을 조금 참고해보았더니 굳이 새로 더하지 않고 하나씩 제외하면 되더라. 가장 앞에 것을 빼고, 다음 걸 더하기 전에 남은 것들로도 target이 넘는지 확인해야 하므로 if-else 문으로 확인하는 로직을 추가했고 그 다음 것이 i번째 인덱스 값이기 때문에 마지막 인덱스까지 확인하기 위해서는 for문의 조건이 i <= nums.length여야 했다. 이 부분에서 암산으로 하다보니 조금 이해하기 힘들었다. 설명이 부족하긴 하지만 이 글을 읽는 누군가는 빠르게 이해할 수 있길...