算法10未排序数组中累加和为给定值的最长子数组系列问题补1

描述

给定一个无序数组arr，其中元素可正、可负、可0。求arr所有子数组中正数与负数个数相等的最长子数组的长度。

[要求]

时间复杂度为O(n)O(n)，空间复杂度为O(n)O(n)

输入描述：

第一行一个整数N，表示数组长度
接下来一行有N个数表示数组中的数

输出描述：

输出一个整数表示答案

示例1

输入：
5
1 -2 1 1 1

输出：
2

思路

正数变1，负数变-1，计算总和为0的最长子数组。

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

public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        HashMap<Integer,Integer> map = new HashMap<>();
        int n = scanner.nextInt();
        int sum=0, val=0, len=0;
        for(int i =0;i<n;i++){
            val = scanner.nextInt();
            if(val>0){
                sum++;
            }else if(val<0){
                sum--;
            }
            // 如果sum刚好为0则数组 [0~i]为最长数组。这里相当于预先在map中加入(0,-1)
            if(sum == 0){
                len = i + 1;
                continue;
            }
            if(map.containsKey(sum)){
                len = len > i-map.get(sum)?len:i-map.get(sum);
            }else{
                map.put(sum,i);
            }
        }
        System.out.println(len);
        scanner.close();
    }
}