ac

给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度

import java.util.Scanner;

public class Main {

    public static Scanner sc = new Scanner(System.in);

    /*
5 0
1 -2 1 1 1

sums
0 1 -1 0 1 2
     */
    public static void main(String[] args) {

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        // sum[j] - sums[i] : 区间：[i, j-1]
        // sum[j + 1] - sum[i] : 区间：[i, j]
        int[] sums = new int[n + 1];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            if(i == 0){
                sums[i + 1] = arr[i];
            }else {
                sums[i + 1] = sums[i] + arr[i];
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int tmp;
                int len = j - i + 1;
                if(len <= ans){
                    continue;
                }
                if(j == i){
                    tmp = arr[i];
                }else {
                    tmp = sums[j + 1] - sums[i];
                }
                if(tmp == k){
                    ans = Math.max(ans, len);
                }
            }
            if(n - i < ans){
                break;
            }
        }
        System.out.println(ans);
    }

}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int sum = 0; // 0位置到i位置所有元素的和
        int len = 0;
        Map<Integer, Integer> mp = new HashMap<>(); // sum,对应最早出现的位置
        mp.put(0, -1);
        for(int i=0;i<n;i++){
            sum += arr[i];
            if(mp.containsKey(sum-k)){
                // 到i位置是sum
                // 到mp.get(sum-k)位置是sum-k
                // 两个位置减一下就是和为k的自数组长度了
                len = Math.max(len, i - mp.get(sum - k));
            }
            if(!mp.containsKey(sum)){
                mp.put(sum, i);
            }
        }
        System.out.println(len);
    }

}
/*
5 0
1 -2 1 1 1

3
*/