LeetCode209-长度最小的子数组

209. 长度最小的子数组

一、题目

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

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

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

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

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

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum
著作权归领扣网络所有。

二、思路及代码

方法一：前缀和+二分查找（官方题解加上自己一些理解）

下面以nums = [2,3,1,2,4,3]为例子。

（1）先创建一个数组sums，负责记录前缀和，其中sums[i]=sums[i-1]+nums[i-1]，如例子中sums = [0,2,5,6,8,12,15]。

（2）遍历sums：在过程中，设置一个target = sums[i-1]+s，然后与sums[i]、sums[i+1]等比较，直到sums[某一个值]大于等于target为止，其目的等价于从对应的nums里第（i-1）这个位置开始遍历求后面数的和，直到大于s为止（这里可以仔细思考思考）。实现这一步是通过lower_bound(sums.begin(), sums.end(), target)，功能是在sums数组里找到比target大的值里的最小值。

（3）当不断出现更短长度的时候，及时更新ans。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
       int ans = INT_MAX;
       if(nums.size() == 0){
           return 0;
       }
       vector<int> sums(nums.size() + 1, 0);
       //求出前i-1项和的数组
       for(int i = 1; i < sums.size(); i++){
           sums[i] = sums[i-1] + nums[i-1];
       }
       //进行检索
       for(int i = 1; i < sums.size(); i++){
            int target = s + sums[i-1];//从第i-1位加s，为了和sums后面的元素进行比较，比较过程如下
            auto bound = lower_bound(sums.begin(), sums.end(), target);//找到sums中大于target的值里的最小值（注意target是在sums[i-1]基础上加上目标值的，所以可以直接在sums中比较）
            if(bound != sums.end()){
                //更新ans
                ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
            }
       }
       return ans==INT_MAX ? 0 : ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：滑动窗口法

（1）设定左右指针，右指针不断向右遍历，同时求从left到right数组元素的和sum。

（2）当这个和大于等于s时，记录下这时候left到right的长度（temp_length），同时left要向右移动，使得sum继续小于s；而right也一直向右移动。

（3）在循环的过程中，要不断更新长度最小值（length）的值，因为最后返回的是这个length。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
      int left = 0;
      int sum = 0;
      int length = INT_MAX;
      int temp_length = 0;
      for(int right = 0; right < nums.size(); right++){
            sum += nums[right];
            while(sum >= s){
                temp_length = right - left + 1;//记录temp_length
                length = temp_length < length ? temp_length : length;//更新length
                sum -= nums[left++];//左边的指针往前移
            }
        }
        return length == INT_MAX ? 0 : length; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18