LeetCode209. Minimum Size Subarray Sum（数组 / 滑动窗口 / 双指针）
- Medium
- Accepted：158,657
- Submissions：466,000
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
链接
https://leetcode.com/problems/minimum-size-subarray-sum/
题意
给定一个包含n个正整数的数组和一个正整数s，找到一个最小长度的且和大于s的子数组，返回其长度，如果不存在，返回0。
类似的题有，LeetCode3. Longest Substring Without Repeating Characters（滑动窗口）
题解
- 暴力解法，两层循环找出所有的子数组，一层循环统计和与长度并更新答案，时间复杂度$O(n^3)$
- 滑动指针，对暴力解法进行优化，实际上我们在计算sum[i, ..., j]时，其中sum[i, ..., j-1]的和已经计算过，我们做了很多次重复计算。其实对于
2 3 1 2 4 3，当对于某个子数组符合要求时，再往后面加是没有必要的，此时数组只会更长。 - 现用两个指针l初始时指向0，r初始时指向-1，其中nums[l, r]表示滑动窗口，用sum来表示[l, r]之间的和，cnt记录长度，那么当$sum<s$时我们就要把r指针右移，否则我们让l指针右移，在循环的过程中如果出现$sum>=s$那么就更新长度cnt，直至循环结束。时间复杂度$O(n)$
- 一个更优雅的暴力，两层循环找出所有的子数组后，无需再编译一次来求和，我们可以使用前缀和来做预处理，求和的操作为$O(1)$，时间复杂度$O(n^2)$，LeetCode上可以通过
- 还有一个优化，针对第二重循环，用来查找以索引i开头的符合条件的子数组，但是我们把这个过程减至O(lgn)，
sums[j] - sums[i] + nums[i] >= s，就是sums[i] >= s + sums[i-1]，实际上就是在sums数组中找一个数sums[i]大于等于s + sums[i-1]，可以通过二分查找完成，简单一点可以使用STL的lower_bound()，时间复杂度$O(nlogn)$
代码
- Runtime: 8 ms, faster than 98.57% of C++ online submissions for Minimum Size Subarray Sum.
- Memory Usage: 2.1 MB, less than 60.66% of C++ online submissions for Minimum Size Subarray Sum.
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int len = nums.size();
// nums[l...r]为滑动窗口
int l = 0, r = -1, sum = 0, cnt = len + 1;
while (l < len)
{
if (r + 1 < len && sum < s)
sum += nums[++r];
else
sum -= nums[l++];
if (sum >= s)
cnt = min(cnt, r - l + 1);
}
if (cnt == len + 1)
return 0;
return cnt;
}
};
// 如果滑动窗口为[l, r)左闭右开，那么：
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int len = nums.size();
// nums[l...r)为滑动窗口
int l = 0, r = 0, sum = 0, cnt = len + 1;
while (l < len && r < len + 1)
{
if (sum < s && r < len)
sum += nums[r++];
else
sum -= nums[l++];
if (sum >= s)
cnt = min(cnt, r - l);
}
if (cnt == len + 1)
return 0;
return cnt;
}
};- Runtime: 140 ms, faster than 12.29% of C++ online submissions for Minimum Size Subarray Sum.
- Memory Usage: 2.1 MB, less than 84.89% of C++ online submissions for Minimum Size Subarray Sum.
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;
int ans = INT_MAX;
vector <int> sums(n);
// 前缀和预处理
sums[0] = nums[0];
for (int i = 1; i < n; ++i)
sums[i] = sums[i-1] + nums[i];
// 双层循环找到所有的子数组
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
int sum = sums[j] - sums[i] + nums[i];
if (sum >= s) // 最短长度，符合要求就可以停止
{
ans = min(ans, (j - i + 1));
break;
}
}
}
if (ans == INT_MAX)
return 0;
return ans;
}
};- Runtime: 7 ms, faster than 84.65% of C++ online submissions for Minimum Size Subarray Sum.
- Memory Usage: 10.4 MB, less than 92.63% of C++ online submissions for Minimum Size Subarray Sum.
class Solution {
private:
int n;
public:
int minSubArrayLen(int target, vector<int>& nums) {
n = nums.size();
int l = 0, r = 0, sum = 0, ans = n + 1;
while (r < n)
{
sum += nums[r++];
while (sum >= target)
{
ans = min(ans, r - l);
sum -= nums[l++];
}
// cout << l << " " << r << " " << sum << " " << ans << endl;
}
return ans == n + 1 ? 0 : ans;
}
};