Leetcode 数组中和为给定值的最长子数组
程序员文章站
2024-02-17 10:41:10
...
题目描述
给定一个数组arr,该数组无序,但每个值均为正数,再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度
例如,arr = [1, 2, 1, 1, 1], k = 3
累加和为3的最长子数组为[1, 1, 1],所以结果返回3
输入
5 3 1 2 1 1 1
输出
3
【思路】
由于全部为正数,可以有这样一个肯定的信息
若当前窗口的值大于K 那么左边界 =》sum-=arr[left++] 因为 right++窗口增大一定更加超过K
若当前窗口的值等于K 那么更新边界 =》sum-=arr[left++] 因为right++一定超过K
若当前窗口的值小于K 那么更新右边界 =》sum+=arr[++right] 因为left++一定更小
总结而言
对于可以使用滑动窗口的问题其特点是:在当前窗口情况下,下一步窗口的移动(边界变化)是确定的
int main()
{
int N,K;
cin>>N>>K;
vector<int> add(N,0);
for(int i=0;i<N;i++)
cin>>add[i];
int l=0;
int r=0;
int sum=add[l]; //初始化滑动窗口的值
int ans=0;
while(r<N)
{
if(sum==K)
{
ans=max(ans,r-l+1);
sum-=add[l++];
}
else if(sum<K)
{
sum+=add[++r]; //先r++ 然后累加到sum
}
else
{
sum-=add[l++]; //最初的左边界值减掉 然后l++
}
}
cout<<ans<<endl;
}
【问题变形】
题目描述
给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k,求arr所有子数组中累加和为k的最长子数组长度
输入描述:
第一行两个整数N, k。N表示数组长度,k的定义已在题目描述中给出 第二行N个整数表示数组内的数
【思路】
这类问题无法使用滑动窗口,因为一个窗口的情况无法确定下一步移动情况
对于该问题的思路是:
采取map<int,int> map[sum]=i 表示 前面i项累积和为sum 即i为累积和为sum的右边界
那么对于第K项:
sum+=arr[k] 如果之前map中存在 map[sum-k] 那么这一段区间的和为K 即通过两段前k项 相减 =》确定符合要求子区间
同时注意一点,由于需要求解最长的区间,因此map[sum]只在第一次赋值,使得区间长度尽可能长
int N,K;
cin>>N>>K;
unordered_map<int,int> mp;
mp[0]=0;
int sum=0;
int temp;
int ans=0;
for(int i=1;i<=N;i++)
{
cin>>temp;
sum+=temp;
if(mp.find(sum-K)!=mp.end())
{
ans=max(ans,i-mp[sum-K]);
}
if(mp.find(sum)==mp.end()) //总是在第一组时候插入 使得那个值尽可能早
mp[sum]=i;
}
cout<<ans<<endl;
上一篇: for循环取出两个数组中的不同值和相同值
下一篇: 简单数据结构。队列,栈,链表
推荐阅读
-
给定一个数组,值可以为正、负和0,请返回累加和小于等于k的最长子数组长度。
-
Leetcode 数组中和为给定值的最长子数组
-
给定值k的最长子数组长度
-
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
-
不重复打印排序数组中相加和为给定值的所有二元组和三元组
-
不重复打印排序数组中相加和为给定值的所有二元组和三元组
-
不重复打印排序数组中相加和为给定值的所有二元组和三元组
-
LeetCode 1 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
找到数组中和为给定值的两个数
-
leetcode:求两数之和,给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。