LeetCode 209 Minimum Size Subarray Sum

nayu1105·2023년 8월 26일

leetcode 알고리즘

LeetCode

목록 보기

12/28

LeetCode 209 Minimum Size Subarray Sum 풀러가기

문제

int 배열 nums와 int target 이 주어진다.

nums의 연속된 숫자의 합이 target보다 크거나 같을 때 연속된 숫자가 가장 짧은 길이를 구해라.

예를 들어, nums =[2, 3, 1, 3, 4, 3] target = 7로 주어졌을 때 [4, 3] 이 7보다 크거나 같은 연속된 숫자 중 가장 길이가 짧다. 이때 이 연속된 숫자의 길이 2를 반환하면 된다.

문제 분석

첫번째 시도

이 문제는 start 와 end 인덱스를 잡아서 target 보다 큰지 작은지 확인하면 됐다.

이중 포문은 모든 경우를 볼 수 있지만, 시간복잡도가 O(N^2)으로 효율이 좋지 못했다.

내가 생각한 아이디어는 누적합처럼, 해당 길이의 합을 가지고 있고, 앞뒤로 조금씩 더해가는 알고리즘을 생각했다.

start = 0, end = 1, sum = nums[0] 을 default 값으로 둔다.
sum이 target보다 작으면 sum에 nums[end]를 더하고, end에 1을 더해준다. (2) 과정을 sum이 target보다 크거나 같아질 때까지 계속 반복한다.

sum이 target보다 크거나 같아지면 end-start를 min값과 비교하며 갱신한다.

sum에서 nums[start]를 빼고, (1)~(3)과정을 다시 한다.

(1)~(4)진행 중에 (2)번 과정에서 end가 nums.length와 같아지면 더 이상 연속합으로 target값을 만들 수 없기에 탐색을 종료하고, min 값을 return 한다.

코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int end = 1;
        int sum = nums[0];        
        int min = Integer.MAX_VALUE;

        while(start<nums.length){
            if(sum >= target){
                if(min > end-start) min =  end - start;
                sum -= nums[start];
                start++;
            }
            else{
                if(end==nums.length) break;
                sum += nums[end];
                end++;
            }
        }   

        return min == Integer.MAX_VALUE ? 0 : min;

    }
}