[1주차] 209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150 

Minimum Size Subarray Sum - LeetCode

---

📝 문제

 100,000 이하인 자연수를 원소로 가지는 nums 배열과, 정수 target 이 주어진다. nums 배열에서 서브배열의 합이 target 이상인 가장 작은 서브배열의 길이를 리턴하라.

 

🎈 풀이

처음에는 정렬을 이용하려고 하였으나, 서브배열을 구하려면 인덱스가 흐트러지지 않아야 한다. 따라서 정렬은 불가능하므로 투 포인터를 이용하기로 했다.

 

시간복잡도: O(n)

공간복잡도: O(1)

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int right = 0;
    int minLength = nums.length + 1;
    int sum = nums[0];
    while (left < nums.length) {
        if (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            if (minLength == 1) return 1;
            sum -= nums[left++];
        } else {
            if (right < nums.length - 1) {
                sum += nums[++right];
            } else if (sum >= target) {
                sum -= nums[left++];
            } else {
                break;
            }
        }
    }

    if (minLength == nums.length + 1) return 0;
    else return minLength;
}

• left는 서브배열의 시작점, right는 서브배열의 끝점, sum은 서브배열 원소의 총 합을 나타낸다.
• minLength 는 지금까지 조건에 맞는 서브배열 중 가장 작은 길이를 저장한다.
• 현재 sum 이 target 이상이면 조건을 만족하므로 minLength와 비교하여 더 작은것을 저장한다.
• 조건을 만족하지 않을 때,
  • 12행: right가 배열 마지막 인덱스에 도달하지 못했다면 right를 오른쪽으로 밀면서 sum에 더한다.
  • 14행: 마지막에 도달하였고, sum이 target 이상이라면 더 작은길이를 구할 가능성이 있음을 뜻한다. left를 오른쪽으로 민다.
  • 16행: sum 이 target 보다 작으면 더 이상 로직은 무의미하므로 break 한다.
• 만약 minLength가 반복 이후에도 초기값이라면 조건에 맞는 서브배열을 찾지 못했다는 의미이므로 0을 리턴한다.

문제 해결 후, 커밋을 위해 IDE에 복사하였는데

해당 조건이 항상 false 이므로 불필요하단다.

right가 오른쪽 끝에 도달함과 동시에 sum >= target 인 상황을 고려한 조건문이었는데 생각해보니 sum >= target이면 이미 7행 true 이므로 해당 조건까지 도달하지 못한다.

 

📈 타 솔루션 참고

타 솔루션에서 반복문 부분이다.

while(j<nums.length){
  sum+=nums[j++];
  while(sum>=target){
      min = Math.min(min, j - i);
      sum-=nums[i++];
  }
}

해결방식은 나와 같으나 조건이 훨씬 간결하다.

내부 while 문을 이용하여, i (내 코드의 left에 해당) 를 조건이 틀릴 때 까지 계속 오른쪽으로 민다.

그러면 간편하게 서브배열 길이의 최솟값을 도출해 낼 수 있다.