LeetCode Daily Question 6

3 月 11 日 每日一题

题目：209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

eg:

1
2
3
4
5
6
7
8
9

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

思路

Sliding Window

本题最快且最容易理解的写法是使用 sliding window。
建立双指针 left 和 right，移动 right 对 total 进行累加。如果 total 大于等于 target，则触发内部 while 循环，调整 res 之后移动 left, total 减去 left 指向的 value。继续移动 right，直到 right 遍历整个数组。时间复杂度为 O(n)。

Binary Search

使用 Binary Search 写法很有趣。
首先新建数组 total[i]，total 数组为升序。

$total[0] = 0$
$total[i] = nums[0] + nums[1] + … nums[i-1]$

对于每一个 i，利用 Binary Search 找到第一个 j ，满足 j < i 并且 total[j] > total[i] - target。并且易得 total[j - 1] <= total[i] - target

$total[j] > total[i] - target$
则 $nums[0] + nums[1] + nums[j - 1] > nums[0] + nums[1] + nums[i - 1] - target$

$total[j - 1] <= total[i] - target$
则 $nums[0] + nums[1] + … + nums[j - 2] <= nums[0] + nums[1] + … + nums[i - 1] - target$

化简后可得
$target > nums[j] + … +nums[i - 1]$
$target <= nums[j - 1] + … nums[i - 1]$

这意味着对于当前的 i - 1，j - 1 到 i - 1 是最短的满足要求的 subarray。再遍历所有可能的 i 之后，就能找到最短的 subarray。
时间复杂度为 O(nlogn) for * binary search
今天一题顶两题，算是补上了昨天的…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//sliding window
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = nums.size() + 1;
        int total = 0;
        int left = 0;
        for(int right = 0; right < nums.size(); right++){
            total += nums[right];
            while(total >= target){
                res = min(res, right - left + 1);
                total -= nums[left];
                left++;
            }
        }
            return (res == (nums.size() + 1)) ? 0 : res;
    }
};

//Binary Search
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int res = size + 1;
        vector<int> sums (size + 1, 0);
        for(int i = 1; i < size + 1; i++){
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for(int i = size; i > 0 && sums[i] >= target; i--){
            int j = upper_bound(sums.begin(), sums.end(), sums[i] - target) - sums.begin();
            res = min(res, i - j + 1);
        }
        return (res == (nums.size() + 1)) ? 0 : res;
    }
};