【滑动窗口】【二分查找】C++算法:和至少为 K 的最短子数组

2023-12-29 19:28

本文主要是介绍【滑动窗口】【二分查找】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++ 实现。

这篇关于【滑动窗口】【二分查找】C++算法:和至少为 K 的最短子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/550465

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig