Leetcode - Minumum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

[balabala] O(N)的做法是两指针法或者叫滑动窗口法， right 向前走直到sum > s, 然后left 向前走直到sum < s, 同时更新minLen. 网上找的O(nlogn) 方法不理解，先备忘着，实现之一如Method3， 实现2参见http://www.tuicool.com/articles/miQVzm3 

 

// Method 2: 伸缩滑动窗口法，O(N), 实现2
    public int minSubArrayLen2(int s, int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int left = 0, right = 0, sum = 0, minLen = nums.length;
        while (right < nums.length) {
            while (sum < s && right < nums.length) {
                sum += nums[right++];
            }
            while (sum >= s && left < right) {
                minLen = Math.min(minLen, right - left);
                sum -= nums[left++];
            }
        }
        return left > 0 ? minLen : 0;
    }
    
    // Method 1: 伸缩滑动窗口法，O(N)，实现1
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int left = 0, right = 0, sum = 0, minLen = nums.length;
        while (left <= right) {
            if (sum < s && right < nums.length) {
                sum += nums[right++];
            } else if (sum < s && right == nums.length) {
                break;
            }
            if (sum >= s) {
                minLen = Math.min(minLen, right - left);
                if (minLen == 1)
                    return 1;
                sum -= nums[left++];
            }
        }
        return left > 0 ? minLen : 0;
    }

// 在不下降的序列中寻找恰好比target小的数出现位置，也即最后一个比target小的数出现的位置
    int binarySearchIncreaseLastSmaller(int l, int r, int target, int * nums) {  
        if (l >= r) return -1;
        while (l < r - 1) {
            int m = l + ((r - l) >> 1);
            if (nums[m] < target) l = m;
            else r = m - 1;
        }
        if (nums[r] < target) return r;
        else if (nums[l] < target) return l;
        else return -1;
    }
 
    // Method 3: O (nlogn)
    int minSubArrayLen(int s, int * nums, int numsSize) {
        int * Sum = (int*)malloc(sizeof(int) * (numsSize + 1)), minL = numsSize + 1;
        Sum[0] = 0;
        for (int i = 1; i <= numsSize; i++) Sum[i] = Sum[i - 1] + nums[i - 1];
        for (int i = 1; i <= numsSize; i++) {
            if (Sum[i] >= s) {
                int k = Sum[i];
                int BeforePos = binarySearchIncreaseLastSmaller(0, i, Sum[i] - s + 1, Sum);
                if (BeforePos != -1 && i - BeforePos < minL) minL = i - BeforePos;
            }
        }
        return minL == numsSize + 1 ? 0 : minL;
    }

 

 

 

 

评论

1 楼 qb_2008 2015-06-10  

O(nlogn)的思路很简单，它就是利用了所有数都是非负数的条件。所以数组num的加和数组sum也是递增的。加和数组（名字不确定，在编程珠玑上见过）定义如下：
sum[0] = num[0];
for (int i = 1; i < n; ++i) {
  sum[i] = sum[i - 1] + num[i];
}

所以sum[i] - sum[j - 1]可以用O(1)时间得到num[j..i]的子序列和。
给定一个下标i, sum[i]确定，找另一个更大的下标j，使sum[j] - sum[i - 1] >= s；或者
找另一个更小的下标j，使sum[i] - sum[j - 1] >= s。因为sum数组是递增的，所以可以
用二分查找。