[Sliding Window] Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 
 * Runtime	: 5725 ms
 * Memory	: 46.38 MB
 */
var minSubArrayLen = function(target, nums) {
  let min = Number.MAX_SAFE_INTEGER;

  for(let i = 0; i < nums.length; i++) {
    let sum = nums[i];

    if(sum >= target) {
      min = 1;
      break;
    }
    
    for(let j = i + 1; j < nums.length; j++) {      
      sum += nums[j];      

      if(sum >= target) {               
        min = Math.min(min, j - i + 1);
        break;
      }      
    }
  }

  return min === Number.MAX_SAFE_INTEGER ? 0 : min;
};

완전 탐색 방법을 사용하였습니다.

1번째 루프 : [[1,2],3,4,5]
2번째 루프 : [[1,2,3],4,5]
3번째 루프 : [[1,2,3,4],5]
4번째 루프 : [[1,2,3,4,5]]
5번쨰 루프 : [1,[2,3],4,5]
6번쨰 루프 : [1,[2,3,4],5]
7번쨰 루프 : [1,[2,3,4,5]]
8번째 루프 : [1,2,[3,4],5]
9번째 루프 : [1,2,[3,4,5]]
10번째 루프: [1,2,3,[4,5]] → 정답

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using sliding window

해답의 전문은 링크를 확인해주세요.

/**
 * Runtime	: 57 ms
 * Memory	: 46.57 MB
 */
var minSubArrayLen = function(target, nums) { 
  let minLength = Infinity; // Initialize the minimum length as positive infinity

  let sum = 0; // Variable to track the current sum
  
  let left = 0; // Pointer for the left end of the subarray
  
  for (let right = 0; right < nums.length; right++) {   
    sum += nums[right]; // Add the current element to the sum
    
    while (sum >= target) {
        minLength = Math.min(minLength, right - left + 1); // Update the minimum length
        sum -= nums[left]; // Remove the leftmost element from the sum
        left++; // Move the left pointer to the right
    }
  }
  return minLength === Infinity ? 0 : minLength; // Return 0 if no subarray is found
};

필자의 해답보다 루프를 덜 도는 해답입니다. 이로써 시간 성능에 큰 영향을 주었습니다.

첫번째 루프: [[1,2,3,4,5]]
두번쨰 루프: [1,[2,3,4,5]]
세번째 루프: [1,2,[3,4,5]]
네번째 루프: [1,2,3,[4,5]] → 정답