首页 > 试题广场 >

未排序数组中累加和为给定值的最长子数组长度

[编程题]未排序数组中累加和为给定值的最长子数组长度
  • 热度指数：6605 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度

输入描述:
第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数


输出描述:
输出一个整数表示答案
示例1

输入

5 0
1 -2 1 1 1

输出

3

备注:

算法知识视频讲解
查看答案及解析
添加回答
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    cin>>n>>x;
    vector<int>res(n);
    for(int i=0;i<n;i++)
        cin>>res[i];
    map<int,int> hm;
	hm[0] = -1;
	int len = 0, sum = 0;
	for (int i = 0; i < res.size(); i++){
		sum += res[i];
		if (hm.find(sum - x) != hm.end())
			len = max(len, i - hm.find(sum - x)->second);
		if (hm.find(sum) == hm.end())
			hm[sum] = i;
	}
	cout<<len;
    return 0;
}

发表于 2019-08-24 22:08:13 回复(0)
橹帆头像 橹帆
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <limits.h>
#include <stdint.h>
#include<stdio.h>
#include <stack>
#include <string>
#include <queue>
#include <functional>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> preSum(n + 1, 0);        // 进行区间求和的优化, 类似sum(i, j) = preSum(j) - preSum(i)
    for (int i = 1; i <= n; ++i)
    {
        int temp;
        cin >> temp;
        preSum[i] = preSum[i - 1] + temp;
    }
    
    int maxLen = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            if (preSum[j] - preSum[i] == k)
            {
                maxLen = max(maxLen, j - i);
            }
        }

        if (maxLen >= n - i)    // 剩下的长度都小于maxLen, 剪枝处理
        {
            break;
        }
    }
    cout << maxLen << endl;

    system("pause");
}
发表于 2019-10-04 08:36:39 回复(1)
牛客第N白菜头像 牛客第N白菜
没有想出更好的方法，只能借鉴一下大神的方法，在这里稍微说一下主要思路：
1.考虑到有正负数存在的情况，要考虑和为0的情况，
2.在遍历数组的循环外声明一个unordered_map，也就是哈希表，用来表示和为sum的最小数组长度
3.遍历数组时，对sum-k对应的哈希值进行查找，如果找到了，说明对应的下标内的前N个值的和+k=当前的sum值，反过来就可以求出当前找到的和为k的数组长度，再与之前的max比较即可求解
以上为个人拙见，希望可以帮助到大家

发表于 2019-08-24 16:01:28 回复(0)
Python
Dayanghe头像 Dayanghe

参考大神方法，使用字典方法

循环遍历每个数字，记录累加结果，找到sums-k

while True:
    try:
        n, k = map(int,input().split())
        inputs = list(map(int,input().split()))
        sums = 0
        res = 0
        dict = {0:-1}
        for i in range(n):
            sums+=inputs[i]
            if sums not in  dict:
                dict[sums]=i
            if sums-k in dict:
                res=max(res,i-dict[sums-k])
        print(res)
    except:break
发表于 2019-08-18 17:09:57 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k, Max=0;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    map<int,int> M;
    M[0] = -1;
    for(int i=0,s=0;i<n;i++){
        s += a[i];
        if(M.find(s-k)!=M.end())
            Max = max(Max, i-M[s-k]);
        if(M.find(s)==M.end())
            M[s] = i;
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2020-02-03 02:24:52 回复(0)
Java
小星教授头像 小星教授 
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
       
         Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int sum = 0,maxLen = 0;
        for(int i=0;i<n;i++){
            sum += arr[i];
            if(!map.containsKey(sum)){
                map.put(sum,i);
            }
            if(map.containsKey(sum-k)){
                maxLen = Math.max(maxLen,i-map.get(sum-k));
            }
            
        }
        
        System.out.print(maxLen);
		
	}
}

发表于 2019-10-24 12:56:25 回复(0)
黄河滴滴66头像 黄河滴滴66 
package com.hhdd.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

/**
 * 求最长子数组的累加和为k
 */
public class MaxLengthAddEqualsK {


    public static int maxLength(int[] arr, int k) {

        if (arr == null || arr.length == 0) {
            return 0;
        }
        //map中的key用来记录累加和，对应的value是这个累加和第一次出现的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        //这个很关键的，当数组从0开始的累加和是k时就会用到，所以一定要保证<0,-1>已经在map中了，这个当前i个和等于k时就用到了
        //当{1，2，3} k = 3时就可以体现出来，好好体会！
        map.put(0, -1);
        //sum用来记录数组前i项的和，length用来记录最后的答案
        int sum = 0, length = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            //看看map中是否已经存过sum-k这个累加和了，有的话从那个值到目前的i就是length了
            if (map.containsKey(sum - k)) {
                int j = map.get(sum - k);
                length = i - j > length ? i - j : length;
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return length;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int k =scanner.nextInt();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        int ans = maxLength(arr,k);
        System.out.println(ans);
    }

}

发表于 2019-09-01 00:17:38 回复(0)
Java
pein531头像 pein531
动态规划求解，用一个哈希表记录前缀和及其出现时的元素位置，当遇到一个没见过的前缀和presum时，就将其加入到哈希表中。如果哈希表中存在presum-k，说明从上一次presum出现的下一个位置到当前位置，数组元素的累加和为k，可以更新最长长度。这里可以看到presum出现的位置在更新最长长度时是需要用的，因此为了保证数组长度尽可能长，对于某个前缀和而言，哈希表中只存储它第一次出现的位置。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(params[i]);
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int presum = 0, maxLen = 0;
        for(int i = 0; i < n; i++){
            presum += arr[i];
            if(map.containsKey(presum - k))
                maxLen = Math.max(maxLen, i - map.get(presum - k));
            if(!map.containsKey(presum))
                map.put(presum, i);
        }
        System.out.println(maxLen);
    }
}

发表于 2021-12-02 22:43:12 回复(0)
C++
麦芒2021头像 麦芒2021
系列题目：
1、未排序数组中累加和为给定值的最长子数组长度
2、未排序数组中正数和负数个数相等的最长子数组长度
3、未排序0-1数组中，0和1个数相等的最长子数组长度
对于本题，arr[i]表示[0,i]的和，并记录到哈希表中，key为和，value为最后一个和为该值的下标。
同样，对于2，将负数全部变成-1，正数全部变成-1，求和为0的最长子数组长度；
对于问题3，将0全部变成-1.
代码如下： 
#include "bits/stdc++.h"

using namespace std;
int main()
{
    int len;cin>>len;
    int target;cin>>target;
    unordered_map<int,int> ump;
    int sum=0;
    int cur;
    vector<int> arr(len);
    for(int i=0;i<len;i++)
    {
        cin>>cur;
        sum+=cur;
        ump[sum]=i;
        arr[i]=sum;
    }
    int ret=0;
    for(int i=0;i<len;i++)
    {
        if(arr[i]==target) ret=max(ret,i+1);
        if((ump.count(target+arr[i])==1)&&ump[target+arr[i]]>i)
        {
            int k=ump[target+arr[i]]-i;
            ret=max(ret,k);
        }
    }
    cout<<ret;
    return 0;
}


发表于 2022-01-10 13:16:30 回复(0)
Go
<云昊>头像 <云昊> 
package main

import (
    "fmt"
)

func main() {
    var (
        n int 
        k int 
        num int
    )
    fmt.Scan(&n,&k)
    arr := make([]int,n)
    for i:=0;i<n;i++ {
        fmt.Scan(&num)
        arr[i] = num 
    }
    result := getMaxLength(arr,k)
    fmt.Printf("%d\n",result)
}

func getMaxLength(arr []int, k int) int {
    if len(arr) == 0 {
        return 0
    }
    length, sum := 0, 0
    m := make(map[int]int)
    //初始化位置
    m[0] = -1
    for i :=0;i<len(arr);i++ {
        sum += arr[i]
        if v,ok := m[sum-k];ok {
            length = max(length,i-v)
        }
        if _,ok := m[sum]; !ok {
            m[sum] = i 
        }
    }
    return length 
}

func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}

发表于 2021-11-14 15:17:37 回复(0)
牛客66319561号头像 牛客66319561号
C++,可以运行并通过。 
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
    int N,k,res=0,sum=0;
    cin>>N>>k;
    map<int,int> map;
    map[0]=-1;
    vector<int> arr(N,0);
    for(int i=0;i<N;++i){
        cin>>arr[i];
    }
    for(int i=0;i<arr.size();++i){
        sum+=arr[i];
        if(map.find(sum)==map.end()){
            map[sum]=i;
        }
        if(map.find(sum-k)!=map.end()){
            res=max(res,i-map[sum-k]);
        }
    }
    cout<<res<<endl;
}


发表于 2021-07-13 10:13:45 回复(0)
Java
眼睛想旅行121头像 眼睛想旅行121 
import java.util.Scanner;
import java.util.HashMap;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(getMaxLength(arr,k));
    }
    public static int getMaxLength(int[] arr,int k){
        if(arr==null||arr.length==0){
            return 0;
        }
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        map.put(0,-1);
        int len=0;
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            if(map.containsKey(sum-k)){
                len=Math.max(i-map.get(sum-k),len);
                
            }
            if(!map.containsKey(sum)){
                map.put(sum,i);
            }
        }
        return len;
    }
    
}

发表于 2021-03-15 14:18:31 回复(0)
Java
寒泉hq头像 寒泉hq 
package test;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        // solution
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxLen = 0, curSum = 0;
        for (int i = 0; i < n; i++) {
            curSum += arr[i];
            if (!map.containsKey(curSum)) {
                map.put(curSum, i);
            }
            int gap = curSum - k;
            if (map.containsKey(gap)) {
                maxLen = Math.max(i - map.get(gap), maxLen);
            }
        }
        System.out.println(maxLen);
    }
}
/*
【示例1】
11 0
1 -2 1 1 1 -1 1 -1 1 -1 2
答案：9
解析：1 [-2 1 1 1 -1 1 -1 1 -1] 2

【示例2】
20 0
-1 1 0 4 5 -2 2 -2 2 -2 2 -4 4 5 -2 -2 -1 1 1 1
答案：12
解析：-1 1 0 4 5 [-2 2 -2 2 -2 2 -4 4 5 -2 -2 -1] 1 1 1
 */

编辑于 2020-12-18 00:00:22 回复(0)
在写日记的钝角很痴心头像 在写日记的钝角很痴心
  1. 多设一个累加和数组 sums，sums[j]-sums[i]可以表达[i, j)区间和
  2. 类似于左右指针的思想，左指针从0->n-1，右指针从n->左指针位置+现有的最大长度（由于只需要找最长的，因此可以直接提高下界）

ps. sums为了处理方便，多加了一个0值

详见代码

#include <bits/stdc++.h>

int main()
{
    int n, k;
    int ret=0;
    std::cin >> n >> k;
    int arr[n];
    int sums[n+1];
    memset(sums, 0, sizeof(sums));
    for(int i=0; i<n; ++i)
    {
        std::cin >> arr[i];
        sums[i+1] = sums[i] + arr[i];
    }
    for(int i=0; i<n; ++i)
    {
        for(int j=n; j-i>ret; --j)
        {
            if(sums[j] - sums[i] == k)
            {
                ret = std::max(ret, j-i);
                break;
            }
        }
    }
    std::cout << ret;
}
发表于 2020-08-18 23:56:49 回复(0)
是兄弟就一起加班头像 是兄弟就一起加班

C++直接处理输入数据


数据读入就处理，不用等到数据读完了再来遍历
有个坑的地方是输出末尾不能加换行，不然只能过60%例子
贴个代码摸个鱼 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    vector<int> v(n+1, 0);
    unordered_map<int,int> m;
    m[0] = 0;
    int res = 0;
    for(int i=1;i<=n;++i){
        cin>>v[i];
        v[i] += v[i-1];
        if(m.find(v[i]-k) != m.end())
            res = max(res, i-m[v[i]-k]);
        if(m.find(v[i]) == m.end())
            m[v[i]] = i;
    }
    cout<<res;
    return 0;
}



发表于 2020-07-18 11:16:25 回复(0)
MashallHe头像 MashallHe
第一种方法采用数组保存前缀和。时间复杂度为 O(n^n) 
#include<vector>
(721)#include<iostream>
#include<map>

using namespace std;
int main(){
    size_t n;
    int k;
    std::cin >> n >> k;
    vector<int> sums(n + 1, 0);
    
    for(int i = 0; i < n; i++){
        int temp;
        std::cin >> temp;
        sums[i + 1] = sums[i] + temp;
    }
    int longest = 0;
    for(int i = 1; i < sums.size(); i++){
        if(sums[i] == k){
            longest = max(longest, i);
        }else{
            for(int j = 1; j < i; j++){
                int subSum = sums[i] - sums[j];
                if(subSum == k){
                    longest = max(longest, i - j);
                    break;
                }else if(i - j <= longest){
                    break;
                }
            }
        }
    }
    std::cout << longest << std::endl;;
    return 0;
    
}

发表于 2020-03-24 11:22:40 回复(1)
罗毅lala头像 罗毅lala 
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> v(N);
	unordered_map<int, int> m;
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
	}
	m.insert(make_pair(0,-1));
	int index = 0;
	int len = 0;
	int sum = 0;
	while (index < N) {
		sum += v[index];
		m.insert(make_pair(sum,index));
		auto it = m.find(sum - K);
		if (it != m.end()) {
			len = max(len, index - (*it).second);
		}
		index++;
	}
	
	cout << len << endl;
    return 0;
}

发表于 2019-11-12 18:16:16 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int  main()
{
    long n,k;
    cin>>n>>k;
    vector<long>v(n+1);
    for(int i=1;i<=n;++i)
        cin>>v[i];
    long long temp;
    int ans = 1;
    for(int i=1;i<=n;++i)
    {
        for(int j=i;j<=n;++j)
        {
            if(j==i)
                temp=v[i];
            else 
            {
                temp+=v[j];
                if(temp==k)
                    ans = max(ans,j-i+1);
            }
        }
        
        // 这步很关键  参考大佬的思路  ，剪枝 时间优化  不然只过70%
        if(ans>n-i)
            break;
    }
    cout<<ans<<endl;   
    return 0;
}

发表于 2019-10-12 23:22:01 回复(0)
拿大offer头像 拿大offer 
import java.util.Scanner;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        String s =sc.nextLine();
        int a = Integer.valueOf(s.split(" ")[0]);
        int number = Integer.valueOf(s.split(" ")[1]);
        int[] arr = new int[a];
        for(int i =0;i<a;i++){
            arr[i] =sc.nextInt();
        }
        returnMaxLength(arr,number);
    }
    public static void returnMaxLength(int[] a,int b){
        int sum =0;
        int len =0;
        HashMap<Integer,Integer>map =new HashMap<>();
        map.put(0,-1);
        for(int i =0;i<a.length;i++){
            sum +=a[i];
            if(map.containsKey(sum -b)){
                len = Math.max(i -map.get(sum -b),len);
            }
            if(!map.containsKey(sum)){
                map.put(sum,i);
            }
        }
         System.out.print(len);
    }
}

发表于 2019-08-28 21:08:17 回复(0)
shineshy头像 shineshy
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    cin.get();
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cin.get();
    int res = (arr[0]==k)?1:0;
    for (int i = 1; i < n; i++)
    {
        arr[i] += arr[i - 1];
        if (arr[i] == k) res = max(res, i + 1);
    }
    for (int i=0;i<n;i++)
        for (int j = n; j > i+res; j--)
        {
            if (arr[j] - arr[i] == k)
            {
                res = max(res, j - i);
                break;
            }
        }
    cout << res << endl;
    return 0;
}
发表于 2019-08-21 20:16:11 回复(0)
提交观点

问题信息

队列
上传者：小小
难度：
21条回答 5388浏览

热门推荐

通过挑战的用户

查看代码

相关试题

未排序数组中累加和为给定值的最长子数组长度

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号