[ Top Interview 150 ] 209. Minimum Size Subarray Sum

문제

209. Minimum Size Subarray Sum

  Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

  A subarray is a contiguous non-empty sequence of elements within an array.

• Input : 양수로 이루어진숫자 배열 nums, 특정 숫자 target
• Output : nums의 부분 배열들에 대해 원소들의 합이 target보다 같거나 큰 부분 배열 중 부분 배열 길이의 최소값
  • 부분 배열은 원배열의 1개 이상의 원소를 포함한 연속적인 구간을 의미

알고리즘 1차 전략

• 1차 전략 (double pointer와 유사하게)

  • front, back을 전부 0을 가리키도록 함
  • sum을 front 부터 back까지의 합으로 구함
    • sum이 target 보다 크거나 같다면 minSize와 비교하여 더 작은 값을 minSize에 할당함, 그 후 front를 앞으로 한칸 이동함
    • sum이 target 보다 작다면 back을 앞으로 한칸 이동함

• 1차 전략의 문제점

  • 매번 sum을 구해야 하기 때문에 Time complexity가 O(n^2)이 된다.

알고리즘 2차 전략

• Sliding Window
  • 해당 문제는 1차원 데이터를 연속적인 구간으로 사용함
  • 구간이 움직이면서 추가/제거 되는 값에 따라 대상값(부분배열 원소의 합)이 규칙적으로 변화한다.
  • Sliding Window를 사용하기 적합하다.
• 해결 전략
  • front, back을 전부 0을 가리키도록 함
  • tempSum을 nums[0]으로 설정함
    • tempSum이 target 보다 크거나 같다면 minSize와 비교하여 더 작은 값을 minSize에 할당함, 그 후 front를 앞으로 한칸 이동, 빠진 원소를 tempSum에서 뺀다.
    • tempSum이 target 보다 작다면 back을 앞으로 한칸 이동, 더해진 원소를 tempSum에서 더한다.

작성 답안 1

• Time complexity : O(n)
• Space complexity: O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minSize = 0;
        int tempSum = nums[0];
        int front = 0;
        int back = 0;

        while(front <= back) {
            if (tempSum < target) {
                if (back >= nums.length - 1) {
                    break;
                }
                back++;
                tempSum += nums[back];
            } else if (tempSum >= target) {
                if (minSize == 0) minSize = back - front + 1;
                minSize = Math.min(minSize, back - front + 1);
                tempSum -= nums[front];
                front++;
            }
        }

        return minSize;
    }
}

작성 답안 2

• 작성 답안 1의 개선점
  • 불필요한 작업 제거 : back, front 차이가 minSize보다 크거나 같은 경우를 체크하지 않는 방법이 있다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        
        int minSize = nums.length + 1;
        int tempSum = nums[0];
        int front = 0;
        int back = 0;

        while(front <= back && (tempSum >= target || back < nums.length - 1)) {
            if (tempSum < target) {
                back++;
                tempSum += nums[back];
                if (minSize <= back - front + 1) { // 크기가 minSize보다 클 때
                    tempSum -= nums[front];
                    front++; // 생각하지 않고 다음으로 넘어간다.
                }
            } else {
                minSize = back - front + 1;
                tempSum -= nums[front];
                front++;
            }
        }

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