[LeetCode] Minimum Size Subarray Sum - Javascript

Minimum Size Subarray Sum

[최소길이의 subarray 구하기]

 

제약 조건 

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

 

Example

ex1) 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.

ex2) Input: target = 4, nums = [1,4,4]
     Output: 1
     
ex3) Input: target = 11, nums = [1,1,1,1,1,1,1,1]
     Output: 0

초기 문제 접근 방식

brute force 방법으로 i와 j를 돌려, i와 j가 더 한 값이 taget보다 크거나 같은지 반복문을 순회한다.
그 과정에서 cnt 변수에 해당 배열의 크기를 담아 두고 cnt의 최솟값을 minimum size로 판단하는 방법을 선택했다.

초기 전체코드

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

      for (let j = i; j < nums.length; j++) {
         sum += nums[j];
         cnt++;
         if (sum >= target) {
            cntArr.push(cnt);
         }
      }
   }

   if (cntArr.length) {
      return Math.min(...cntArr);
   }
   return 0;
};

 

해당 코드로 주어진 아래의 testcase 3개를 모두 통과하여 제출을 했다.

ex1) Input: target = 7, nums = [2,3,1,2,4,3]
     Output: 2
     
ex2) Input: target = 4, nums = [1,4,4]
     Output: 1
     
ex3) Input: target = 11, nums = [1,1,1,1,1,1,1,1]
     Output: 0

다시 생각 해보며..

하지만 전체의 21개의 testcase 중 18개밖에 통과를 하지 못했고, 타임아웃에 걸려 문제를 풀지 못했다.

아마 이중 for문을 사용 해 시간 복잡도가 O(n^2)가 되어 타임아웃에 걸린듯 했다. 

brute force 방법을 사용하지않고, slice window기법으로 풀어야겠다 생각했다.

solve 전체 코드

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

   while (right < nums.length) {
      sum += nums[right];

      while (sum >= target) {
         size = right - left + 1;
         min = Math.min(min, size);
         sum -= nums[left];
         left++;
      }
      right++;
   }
   if (min > nums.length) {
      return 0;
   } else {
      return min;
   }
};

sum 변수에 nums 배열의 인덱스를 하나하나 더한 값이 target보다 크거나 같을 때까지 반복문을 수행한다.
더 큰 값이 들어왔다면 nums 배열의 맨 왼쪽 인덱스를 하나씩 제거하고 mininum size를 min 변수에 저장한다.
즉 2,3,1,2를 더한 값은 8이고 sum -= nums[left]를 통해 3,1,2 또한 target보다 큰 값이 될 수 있는지 비교한다.
될 수 없다면 맨 왼쪽 인덱스를 sum 값에서 제거하고 그다음 오른쪽 인덱스를 추가 하여 더 한다.  ([3, 1, 2, 4]를 더 함)

이 과정을 반복 해 가장 작은 min 값을 가질 때 까지 반복한다.

 

min의 값이 nums.length보다 크다 면 배열에 있는 값을 모두 더해도 target 수 보다 클 수 없다는 의미기에 0을 리턴한다.