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

[编程题]未排序数组中累加和为给定值的最长子数组长度

热度指数：8361 时间限制：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

输出

备注:

算法知识视频讲解

查看答案及解析

Java

_止水_

使用前缀和+哈希的方法，并且把最长的任意区间转化为0-i内的前缀和最小

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int MAXN = 100001;

    public static int[] arr = new int[MAXN];

    public static int n, aim;

    // key : 某个前缀和
    // value : 这个前缀和最早出现的位置
    public static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            aim = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            out.println(compute());
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int compute() {
        map.clear();
        // 重要 : 0这个前缀和，一个数字也没有的时候，就存在了
        map.put(0, -1);
        int ans = 0;
        for (int i = 0, sum = 0; i < n;
                i++) {  /// 在循环中求解 以i为结尾的子数组的最大长度
            sum += arr[i]; /// 当前的总的 sum
            if (map.containsKey(sum - aim)) {
                //     60         i   到达i时候的和是100，aim=40
                // 0...13  14  15 16         /// 16-13
                ans = Math.max(ans, i - map.get(sum - aim)); /// 求最大长度
            }
            if (!map.containsKey(
                        sum)) {  /// 只有不包含才进行加入，因为map记录的是最早的，第一次
                map.put(sum, i);
            }
        }
        return ans;
    }
}

发表于 2025-03-12 15:59:02 回复(0)

Java

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)

Java

眼睛想旅行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

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)

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)