[leetCode 209번] Minimum Size Subarray Sum (Java)

1.문제

Minimum Size Subarray Sum - LeetCode

Minimum Size Subarray Sum - LeetCode

---

2.문제설명

 

이 문제는 주어진 배열에서 target 값의 최소 길이를 반환 해주면 되는 문제이다.

---

3.소스코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
            int p1 = 0;
            int sum = 0;

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

                while (sum >= target) {
                    minLen = Math.min(minLen, i - p1 + 1);
                    sum -= nums[p1];
                    p1++;
                }
            }
            if(minLen == Integer.MAX_VALUE){
                return 0;
            }else {
                return minLen;
            }
    }
}

---

4.소스코드 해설

 

문제를 해결 하기 위해서 구간합을 지정 해줘야할 포인터 p1 을 선언한다.

슬라이딩 윈도우 기법을 통해  반복문을 통해 최소 길이를 Math.min()을 통해 최소길이를 정해 준다.

sum 을 구할 때 sum이 target값 보다 클 경우 sum을 포인터 p1 첫 위치의 값을 빼고 p1을 증가 시켜 윈도우의 크기를 옮겨준다.

 

---

5.회고

 

이 문제를 처음 읽고 이해 했을 때는 처음 생각 한것은 DFS 방식으로 체크 하며서 원하는 target일때 리턴을 하는 방식이 어떨가라른 생각 을 하였다 . 하지만 슬라이딩 윈도우를 사용하여 for문 하나로 접근 한다면 속도와 메모리 관련하여 더욱 더 좋을것이라 판단하여 풀었다. 

만약 DFS 로 푼다면 체크 할때마다 스택에 쌓여 메모리와 속도에서는 이문제는 슬라이딩 윈도우를 사용하는것이 좋을것 같다고 생각했다.