【LeetCode题解】LeetCode 209. 长度最小的子数组

【题目链接】
209. 长度最小的子数组
【题目描述】

【题解】

方法一：滑动窗口

本题可以使用双指针算法，定义两个指针l和r分别表示子数组的开始位置和起始位置，sum数组存储的从l到r区间内所有元素的和。初始状态下，l和r都指向下标0，sum的值为0。
每一轮迭代，将nums[r]添加到sum中，如果sum≥target，则更新子数组的最小长度，此时的最小长度为r-l+1，然后将nums[l]从sum中减去并将l右移，直到sum＜target，在这个过程中同样需要更新子数组的最小长度。
在每一轮迭代后，将r右移。
【AC代码】

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int l = 0, r = 0, n = nums.size();int sum = 0, res = 1e9;while(r < n) {sum += nums[r];while(sum >= target) {res = min(res, r - l + 1);sum -= nums[l];l++;}r++;}if(res == 1e9)return 0;return res;}
};

方法二：前缀和+二分查找

阅读题目可以发现，其中出现了子数组的和，而前缀和算法可以在常数时间内通过前缀和数组计算任意区间的和，避免重复计算，从而提高查询效率。同时，这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。
为了使用二分查找，需要额外创建一个数组sums用于存储数组nums的前缀和，其中sums[i]表示从nums[0]到nums[i−1]的元素和。得到前缀和之后，对于每个开始下标i，可通过二分查找得到大于或等于i的最小下标left，使得sums[left]−sums[i−1]≥target，并更新子数组的最小长度（此时子数组的长度是left−(i−1)）。由于二分查找的终止条件是left==right，因此此处找到的最小下标为right或者left。
【AC代码】

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();if (n == 0) return 0;int res = 1e9;vector<int> sums(n + 1, 0);for (int i = 1; i <= n; ++i) {sums[i] = sums[i - 1] + nums[i - 1];}// 提前判断整个数组和是否小于target，直接返回0if (sums[n] < target)return 0;for (int i = 1; i <= n; i++) {int left = i, right = n;while (left < right) {int mid = left + right >> 1;if (sums[mid] - sums[i - 1] >= target) {right = mid;} else {left = mid + 1;}}// 检查left是否有效，且对应的和满足条件if (left <= n && sums[left] - sums[i - 1] >= target) {res = min(res, left - i + 1);}}return res == 1e9 ? 0 : res;}
};

【思考&收获】
1.阅读题目，题目要求的是大于等于target的数组，第一次读题的时候看成了等于target，卡住了一段时间。
2.数组中每个元素都为正，则前缀和一定是递增的，这一点保证了二分的正确性，可以考虑使用二分查找。