目录

LeetCode 209: 长度最小的子数组题目描述解题双指针循环二分查找

LeetCode 209: 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

【示例】

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

【进阶】

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题

双指针

    首先最容易想到的是自然暴力法，从当前位置的元素开始，向右计算累加和，直到遇到数组边界或累加和大于等于目标值停下，如果累加和大于等于目标值，则计算当前子数组的长度，然后向右移动一个元素，继续循环。     暴力法中有较大的计算冗余，用$a_i$表示数组中的元素，假如目前计算表明$a_i$到$a_j$的累加和$S_{i,j}>target$，在下一个循环中，从$a_{i+1}$开始计算时，$a_{i+1}$到$a_j$的累加和$S_{i+1,j}$实际上已经计算过了，因此可以避免对这部分求和，直接用$S_{i,j}-a_i$代替求和阶段。在实现时可以分别用i和j表示左端点位置和右端点位置，即双指针法：

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int cur_sum = 0; int min_len = 0; int i=0, j=0; while (j < nums.size()){ while (j < nums.size() && cur_sum < s){ cur_sum += nums[j]; ++j; } while (cur_sum >= s){ min_len = min_len==0 ? j-i : min(min_len, j-i); cur_sum -= nums[i]; ++i; } } return min_len; } };

循环二分查找

    当题目要求$nlogn$时间复杂度时，我只想到二分查找+循环这种方式，具体怎么用直到看了leetcode的官方解题才意识到还有这种思路，只能说见识还不够。这里引用别人一句话：涉及连续子数组的问题，我们通常有两种思路：一是滑动窗口、二是前缀和。 滑动窗口即上面的双指针法，前缀和就是接下来要说明的方法。     如果$S_i$表示数组从第一个元素到i位置元素的累加和，那么可以构造一个由$S_i$组成的新数组，其中$S_0=0$。这时候可以发现$S_j-S_i$表示$a_{i+1}$到$a_j$的累加和。如果在新数组中查找不小于$S_i+s$的第一个数，得到的结果为$S_j$的话，即表示$a_{i+1}$到$a_j$的累加和大于等于$s$。由于$S_i$数组从左向右时依次递增的，所以可以用更快捷的二分查找（这里也说明一个问题，如果原数组数组不是正整数数组，那这个方法就不太适用了）。

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { size_t len = nums.size(); vector<int> sums(len+1, 0); for (size_t i=0; i<len; ++i){ sums[i+1] = sums[i]+nums[i]; } /*注释这部分的代码与下面for循环语句等效的，但是下面的语句更好看 auto i = sums.begin(), j=sums.begin(); int min_len = 0, cur_len; while (1){ j = lower_bound(i, sums.end(), *i+s); if (j != sums.end()){ cur_len = j-i; min_len = min_len == 0 ? cur_len : min(cur_len, min_len); ++i; } else break; }*/ int min_len = 0; for (int i=1; i<=len; ++i){ auto iter = lower_bound(sums.begin(), sums.end(), sums[i-1]+s); if (iter != sums.end()) min_len = min_len==0 ? static_cast<int>(iter-sums.begin()-i+1) : min(static_cast<int>(iter-sums.begin()-i+1), min_len); } return min_len; } };