Easy to understand O(n log n) solution


  • 0
    M
    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            if(nums == null || nums.length == 0)
                return 0;
                
            int[] partialSum = new int[nums.length + 1];
            partialSum[0] = 0;
            for(int i = 1; i < partialSum.length; i++) {
                partialSum[i] = partialSum[i-1] + nums[i-1];
            }
            
            int min = nums.length + 1;
            for(int i = 1; i < partialSum.length; i++) {
                int lo = i;
                int hi = partialSum.length - 1;
                while(lo <= hi) {
                    int mid = lo + (hi - lo) / 2;
                    int subArraySum = partialSum[mid] - partialSum[i - 1];
                    if(subArraySum >= s) {
                        min = Math.min(min, mid - i + 1);
                        hi = mid - 1;
                    }else{
                        lo = mid + 1;
                    }
                }
            }
            
            return min != nums.length + 1? min : 0;
        }
    }
    

    For every index just binary search the rest of the array for the subarrays that meet the desired constraint.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.