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

[编程题]未排序数组中累加和为给定值的最长子数组系列问题补2

热度指数：2145 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

[要求]

时间复杂度为

，空间复杂度为

输入描述:

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

输出描述:

输出一个整数表示答案

示例1

输入

5
1 0 1 0 1

输出

备注:

算法知识视频讲解

Java

pein531

这个跟匹配括号的过程有点像，定义一个平衡因子balance，遇到一个1就自增，遇到一个0就自减。遍历数组更新这个平衡因子，用一个哈希表记录0~i位置的平衡因子，我们可以知道对于一段数组arr[0:j]，如果它的平衡因子为balance，且存在某个前面的位置i<j，满足arr[0:i]的平衡因子也是balance，这就说明子数组arr[i+1:j]的0和1数量相等，平衡因子归零，可以更新一次长度。

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));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(strArr[i]);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxLen = 0, balance = 0;
        for(int i = 0; i < n; i++){
            balance += arr[i] == 1? 1: -1;
            if(map.containsKey(balance)){
                // 0和1达到平衡时就更新长度
                maxLen = Math.max(maxLen, i - map.get(balance));
            }else{
                map.put(balance, i);
            }
        }
        System.out.println(maxLen);
    }
}

发表于 2021-12-09 17:11:51 回复(0)

Java

眼睛想旅行121

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

public class Main {
  	public static int getMaxLength(int[] arr) {
        int len = 0, sum = 0, k = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i] == 0 ? -1 : 1;
            if (map.containsKey(sum - k)) {
                len = Math.max(len, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return len;
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(getMaxLength(arr));
    }
}

发表于 2021-03-15 14:28:59 回复(0)