Leetcode209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1≤target≤1091 \leq target \leq 10^9
  • 1≤nums.length≤1051 \leq nums.length \leq 10^5
  • 1≤nums[i]≤1051 \leq nums[i] \leq 10^5

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题方法

方法一 滑动窗口法

思路详述

这道题可能最先想到的方法就是滑动窗口法了。也是目前最优的解法。

定义两个指针left和right分别指向窗口的起始位置和结束位置，然后再维护一个变量sum记录窗口中的元素的和。

在开始的时候，left和right分别指向0，并且sum初始化为下标为0的元素的值。

然后将窗口向右滑动遍历整个数组，直到right指向最后一个元素。在遍历的过程中，判断sum和target的值：

  • 如果sum<targetsum < target，那么说明窗口里面的值比目标值要小，需要扩大窗口的大小，right指针向右移动一位，然后更新sum；
  • 如果sum≥targetsum \geq target，那么说明窗口里面的值比目标值要大，首先更新最小的长度，然后需要缩小窗口的大小，left指针向右移动一位，然后更新sum；

详细细节可以参见示例代码。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int minSubArrayLen(int target, vector<int>& nums){
    if(nums.empty()) return 0;

    int left = 0, right = 0;
    int sum = nums[0];
    if(sum >= target) return 1;

    int ans = INT32_MAX;
    while(right < nums.size()){
        if(sum < target){
            right++;
            if(right < nums.size()){
                sum += nums[right];
            }
        }else{
            ans = right -left + 1 > ans ? ans : right -left + 1;
            sum -= nums[left++];
        }

    }
    return ans == INT32_MAX ? 0 : ans;
}

复杂度分析

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1)

方法二 二分查找法

思路详述

这道题容易想到滑动窗口法，但是要找出O(nlogn)O(nlogn)的解法却不容易。

一般而言，O(nlogn)O(nlogn)的解法和二分查找联系很紧密。这道题可以用暴力法来解决，对于每一个元素，从它开始寻找符合条件的子数组，并且记录下长度，从中筛选出最小的长度即可。但是这需要两层循环，要想进行优化，那么就需要对第二层循环查找子数组的过程进行进一步的处理以便可以使用二分查找。

定义一个额外的数组sums来存储nums数组的前缀和，也就是说，nums[i]表示从nums[0]到nums[i-1]的元素和，即nums数组前i个元素的和。通过前缀和的特性，再加上nums数组中元素均为整数，那么sums数组一定是递增的。此外，通过前缀和，我们也可以得到任意连续子数组的和。比如，对于sums[k]和sums[s]，那么sums[s] - sums[k]就可以表示从k+1个数到s个数的和。我们也可以利用这个特性，将target + sums[i - 1]作为新的目标数，通过二分查找可以找到一个比新的目标数大的数中最小的那个的下标new_index，那么new_index - (i - 1)就是比s大的数组的长度。

具体细节可以参见示例代码。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minSubArrayLen(int target, vector<int>& nums){
    if(nums.empty()) return 0;


    vector<int> sums(nums.size() + 1, 0);
    for(int i = 1; i <= nums.size(); ++i){
        sums[i] = sums[i - 1] + nums[i - 1];
    }

    int ans = INT32_MAX;
    for(int i = 1; i <= nums.size(); ++i){
        int s = sums[i - 1] + target;
        auto index = lower_bound(sums.begin(), sums.end(), s);
        if(index != sums.end()){
            ans = min(ans, static_cast<int>((index - sums.begin()) - (i - 1)));
        }
    }

    return ans == INT32_MAX ? 0 : ans;
}

至于在int s = sums[i - 1] + target;中为什么用的是下标i - 1而不是i，主要是有两个原因：

  • 下标i从1开始，也就是对于第一个元素，他也可能包含在符合条件的子数组中，而假设二分查找得到的新下标为new_index，那么符合条件的子数组就是$sums[i + 1],sums[i+2], \cdots , sums[new_index] $。那么要把第一个元素包括进去，那么就必须从i-1开始；
  • i的值最高可以取到nums.size()，但是最后一个元素也可能一个元素组成子数组符合条件，那么同第一个原因，下标必须用i-1。从另一个角度讲，如果用下标i，那么最后一个元素就不可能成为符合条件的子数组的元素，循环就冗余了一次。因而下标必须用i-1；

复杂度分析

时间复杂度：O(nlogn)O(nlogn)

空间复杂度：O(n)O(n)