ac

给定一个无序数组arr，其中元素只能是1或0。求arr所有的子数组中0和1个数相等的最长子数组的长度。

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[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            if(arr[i] == 0){
                arr[i] = -1;
            }
        }
        int k = 0;
        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
1 0 1 0 1

4
*/