Leetcode 209) Minimum Size Subarray Sum

29 Sep 2021 in Algorithms

My Answer

• 간단한 논리, SUM 인동안 LEFT를 POP해버리기.
• 아마 모든 어레이 내의 원소가 양수라서 이렇게 해도 되는듯 싶음.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum=0;
        int min =Integer.MAX_VALUE;
        int left=0;
        int ptr = 0;
        while(ptr<nums.length){
            sum+=nums[ptr];
            ptr++;
            while(sum>=target){
                sum-=nums[left];
                left++;
                min= Math.min(min,ptr+1-left);
            }
        }

        if(min!=Integer.MAX_VALUE){
            return min;
        }else{
            return 0;
        }
    }
}

Other Answer

• BS로 한 예시.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if(nums[0] >= target) return 1;
        else if(nums.length == 1) return 0;
        
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 1;
        int curr = nums[left] + nums[right];
        
        while((left != nums.length - 1) || (right != nums.length - 1)){
            if(curr >= target){
                min = Math.min(right - left + 1, min);
            }
            if(curr < target && right + 1 < nums.length){
                right++;
                curr+=nums[right];
            }
            else if(((curr >= target) || (right == nums.length - 1)) && left + 1 < nums.length){
                curr-=nums[left];
                left++;
            }
        }
        if(curr >= target){
            min = Math.min(right - left + 1, min);
        }
        if(min == Integer.MAX_VALUE) return 0;
        return min;
    }
}