欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;

 

相关标签: Leetcode