二分查找|滑动窗口|前缀和|LeetCode209: 长度最小的子数组

长度最短的子数组

作者推荐

【动态规划】【广度优先】LeetCode2258:逃离火灾

本文涉及的基础知识点

二分查找算法合集
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
滑动窗口

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

枚举开始，二分结尾

时间复杂度：O(nlogn)。
vPreSum是前缀和，已知i，求子数组[i,j)的和大于等于target的最小j。
子数组[i,j)的和等于vPreSum[j]-vPreSum[i] ,大于等于target，则vPreSum[j] >= target + vPreSum[i]，我们选择第一个大于等于target + vPreSum[i]的数。

核心代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {vector<long long> vPreSum = { 0 };for (const auto& n : nums){vPreSum.emplace_back(n + vPreSum.back());}int iRet = INT_MAX;for (int i = 0; i < nums.size(); i++){int j = std::lower_bound(vPreSum.begin(), vPreSum.end(), target + vPreSum[i]) - vPreSum.begin();if (vPreSum.size() == j){continue;}iRet = min(iRet,j-i );}return (INT_MAX== iRet)? 0 : iRet;}
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{int target;vector<int> nums;{Solution slu;target = 7, nums = { 2, 3, 1, 2, 4, 3 };auto res = slu.minSubArrayLen(target, nums);Assert(2, res);}{Solution slu;target = 4, nums = { 1,4,4 };auto res = slu.minSubArrayLen(target, nums);Assert(1, res);}{Solution slu;target = 11, nums = { 1,1,1,1,1,1,1,1 };auto res = slu.minSubArrayLen(target, nums);Assert(0, res);}//CConsole::Out(res);
}

二分长度，利用滑动窗口求和

时间复杂度：O(nlogn)。
首先处理特殊情况：不存在合乎要求的子数组。
寻找第一个符合的长度，用左开右闭的二分。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {if (std::accumulate(nums.begin(), nums.end(), 0LL) < target){return 0;}//左开右闭空间int left = 0, right = nums.size();while (right - left > 1){const int mid = left + (right - left) / 2; auto Is = [&](){				long long llSum = 0;int i = 0;for (; i < mid; i++){llSum += nums[i];}if (llSum >= target){return true;}for (; i < nums.size(); i++){llSum += nums[i] - nums[i - mid];if (llSum >= target){return true;}}return false;};if (Is()){right = mid;}else{left = mid;}}return right;}
};

滑动窗口

两层枚举，第一层从大到小枚举left，第二层枚举right。两层时间复杂度都是O(n)，第二层枚举没有从新开始，所以总时间复杂度是O(n)。子数组[left,right)是以下情况之一：
一，[left,right)是第一个小于target的right。
二，right是m_c。对应没有符合要求的以left开始的子数组。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {m_c = nums.size();long long llSum =0;int iRet = INT_MAX;for (int left = m_c - 1, right = m_c; left >= 0; left--){llSum += nums[left];while (llSum >= target){right--;llSum -= nums[right];}if (m_c != right){iRet = min(iRet, right - left + 1);}}return (INT_MAX==iRet)?0:iRet;}int m_c;
};