【滑动窗口】【二分查找】C++算法:和至少为 K 的最短子数组
作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本题涉及知识点
滑动窗口 有序向量 二分查找
LeetCode862:和至少为 K 的最短子数组
给你一个整数数组 nums 和一个整数 k ,找出 nums 中和至少为 k 的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回 -1 。子数组 是数组中 连续 的一部分。
示例 1:
输入:nums = [1], k = 1
输出:1
示例 2:
输入:nums = [1,2], k = 4
输出:-1
示例 3:
输入:nums = [2,-1,2], k = 3
输出:3
提示:
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109
滑动窗口
时间复杂度O(nlogn)。枚举子数组的结尾时间复杂度O(n),计算最佳开始时间复杂度O(logn)。
vPreSum是前缀和。
nums[l,r]的和为vPreSum[r+1]-vPreSum[l] >= k ==>> vPreSum[r+1] - k >= vPreSum[l]
l取值范围:[0,r]。
最短子数组,也就是l最大。也就是满足 vPreSum[l] <= vPreSum[r+1] - k的最大l。
如果l1 < l2 ,且vPreSum[l1] >= vPreSum[l2] ,则l1被淘汰,l2 被淘汰后 vPreSum成升序。我寻找最后一个小于等于vPreSum[r+1] - k的索引。 用std::upper_bound 。
代码
核心代码
//默认升序
template<class T = long long,bool bAsc= true >
class COrderValueIndexVector
{
public:
COrderValueIndexVector(const vector<T>& vValue):m_vValue(vValue)
{
}
void AddIndex(int index)
{
if (bAsc)
{
Add<std::less_equal<T>>(index);
}
else
{
assert(false);
}
}
//升序:最后一个小于等于的索引
int PreUpperBoundIndex(T value)
{
const int inx = std::upper_bound(m_vOrderValue.begin(), m_vOrderValue.end(), value) - m_vOrderValue.begin();
if (inx > 0)
{
return m_vInx[inx - 1];
}
return -1;
}
protected:
template<class _PR>
void Add(int index)
{
//nums[l,r]的和为vPreSum[r+1]-vPreSum[l] >= k =>vPreSum[r+1] - k >= vPreSum[l]
while (m_vOrderValue.size() && _PR()(m_vValue[index], m_vOrderValue.back()))
{
m_vInx.pop_back();
m_vOrderValue.pop_back();
}
m_vInx.emplace_back(index);
m_vOrderValue.emplace_back(m_vValue[index]);
}
vector<int> m_vInx;
vector<T> m_vOrderValue;
const vector<T>& m_vValue;
};
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
vector<long long> vPreSum = { 0 };
for (const auto& n : nums)
{
vPreSum.emplace_back(n + vPreSum.back());
}
COrderValueIndexVector ov(vPreSum);
int iRet = INT_MAX;
for (int r = 0; r < nums.size(); r++)
{
//nums[l,r]的和为vPreSum[r+1]-vPreSum[l] >= k =>vPreSum[r+1] - k >= vPreSum[l]
ov.AddIndex(r);
const int left = ov.PreUpperBoundIndex(vPreSum[r + 1] - k);
if (left >= 0 )
{
iRet = min(iRet, r - left + 1);
}
}
return (INT_MAX == iRet) ? -1 : iRet;
}
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
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]);
}
}
int main()
{
vector<int> nums;
int k;
{
Solution sln;
nums = { 1 }, k = 1;
auto res = sln.shortestSubarray(nums, k);
Assert(1, res);
}
{
Solution sln;
nums = { 1,2 }, k = 4;
auto res = sln.shortestSubarray(nums, k);
Assert(-1, res);
}
{
Solution sln;
nums = { 2,-1,2 }, k = 3;
auto res = sln.shortestSubarray(nums, k);
Assert(3, res);
}
//CConsole::Out(res);
}
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用C++ 实现。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!