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

题目描述

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

输入描述:

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

输出描述:

输出一个整数表示答案

示例1

输入
5 0
1 -2 1 1 1

输出
3

解题

解题思路：
这道题目最开始的时候我觉得还是比较简单，直接用两个循环遍历所有子数组，同时更新len。但是测试的时候发现case通过率只有70%，然后超时了，果然，没有免费的午餐！

然后看了其它人巧妙方法：
用一个单循环去遍历数组，遍历的同时将累加和依次保存在hashmap中，key表示依次的累加和，value表示累加和对应的下标。核心思想如下：
令i表示子数组的左下标，令j表示子数组的右下标，令$s_j$表示从$0-j$的累加和，$s_i$表示$0-i$的累加和，那么$s_j-s_$表示从$i-j$子数组的累加和。这些累加和及其下标都保存在hashmap中，每遍历一个元素进行一次检测即可。

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        int[] arr = new int[n];
        int j = 0;
        for(String i:in.readLine().split(" ")){
            arr[j++] = Integer.parseInt(i);
        }
        System.out.println(getLength2(arr,k));
        
    }

    //case通过率70%,然后超时
    static int getLength(int[] arr,int k){
        int len = 0;
        int sum = 0;
        for(int left=0;left<arr.length;left++){
            sum = 0;
            for(int right=left;right<arr.length;right++){
                sum += arr[right];
                if(sum == k){
                    len = Math.max(len,right-left+1);
                }
            }
        }
        return len;
    }
    
    static int getLength2(int[] arr,int k){
        int len = 0;
        int sum = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
	    //将新的累加和添加到map中，重复的就不需要了，map中只保存最早的累加和
            if(!map.containsKey(sum))
                map.put(sum,i);
	    //检测是否有满足k值的子数组
            if(map.containsKey(sum-k))
                len = Math.max(i - map.get(sum-k),len);
        }
        
        return len;
    }
}

拓展问题

拓展问题1
给定一个无序数组arr，其中元素可正、可负、可0。求arr所有子数组中正数与负数个数相等的最长子数组的长度。
[要求]
时间复杂度为O(n)，空间复杂度为O(n)
解题思路
题目要求的是正数和负数相等，如果我们将正数修改为1、负数修改为-1，那么当子数组的和为0时，该题也就转化成上面的原题形式。

拓展问题2
给定一个无序数组arr，其中元素只能是1或0。求arr所有的子数组中0和1个数相等的最长子数组的长度
[要求]
时间复杂度为O(n)，空间复杂度为O(n)
解题思路
将数组中所有的0修改成-1，该题同样可以变成原题形式。