209. Minimum Size Subarray Sum

문제

https://leetcode.com/problems/minimum-size-subarray-sum/description/

풀이

    class Solution {

      public int minSubArrayLen(int target, int[] nums) {
        int lt = 0;
        int sum = 0;
        int answer = Integer.MAX_VALUE;

        for (int rt = 0; rt < nums.length; rt++) {
          sum += nums[rt];
          while (sum >= target) { // sum이 크다면 모두 만족하는 subarray
            answer = Math.min(answer, rt-lt+1);
            sum -= nums[lt];
            lt++;
          }
        }
        if (answer == Integer.MAX_VALUE) {
          return 0;
      }
       return answer;
    }
 }

• 만족하는 subarray 중 최소 길이 subarray의 length를 구하는 문제
  • 배열 내에서 가능한 모든 subarray를 O(N)으로 탐색하여 최소 길이를 구해야한다.
    => Sliding window 사용!
• for문 내에서 rt를 1씩 늘려가면서 가능한 subarray를 전부 탐색
  • 만약, sum이 target 이상이라면, 조건을 만족하는 subarray이므로,
    해당 subarray의 길이가 최소값인지 확인한 후,
    lt를 한 칸씩 이동
• for문을 나와서도 answer가 Integer.MAX_VALUE라면, 조건을 만족하는 subarray를 못 찾은 것이므로 0 return

• 시간 복잡도 O(N)
  • rt와 lt 모두 O(N)번씩만 움직이기 때문에 O(2N) -> O(N)
  • rt도 배열을 전체 한 번 돌고, lt도 배열을 전체 한 번 돎