长度最短的子数组
作者推荐
本文涉及的基础知识点
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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
枚举开始，二分结尾
时间复杂度：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; };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
