二分查找|滑動窗口|前綴和|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;
};

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者操作系統：win10 開發環境：

VS2022 C++17

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/212763.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/212763.shtml
英文地址，請注明出處：http://en.pswp.cn/news/212763.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！