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

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

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

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

[要求]

时间复杂度为

，空间复杂度为

输入描述:

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

输出描述:

输出一个整数表示答案

示例1

输入

5
1 -2 1 1 1

输出

备注:

算法知识视频讲解

Java

pein531

和第CD11思路相同，把正数视为1，负数视为0。定义一个平衡因子balance，遇到一个正数就自增，遇到一个负数就自减，遇到零就直接跳过。遍历数组更新这个平衡因子，用一个哈希表记录0~i位置的平衡因子，我们可以知道对于一段数组arr[0:j]，如果它的平衡因子为balance，且存在某个前面的位置i<j，满足arr[0:i]的平衡因子也是balance，这就说明子数组arr[i+1:j]的正数和负数数量相等，平衡因子归零，可以更新一次长度。

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().trim());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(strArr[i]);
        }
        int balance = 0, maxLen = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for(int i = 0; i < n; i++){
            if(arr[i] == 0) continue;
            balance += arr[i] > 0? 1: -1;
            if(map.containsKey(balance)){
                maxLen = Math.max(maxLen, i - map.get(balance));
            }else{
                map.put(balance, i);
            }
        }
        System.out.println(maxLen);
    }
}

发表于 2021-12-09 17:18:52 回复(0)

Java

眼睛想旅行121

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[] arr = new int[n];
        int j = 0;
        for(String i:in.readLine().split(" ")){
            arr[j++] = Integer.parseInt(i);
        }
        System.out.println(getLength(arr));
        
    }
    
    static int getLength(int[] arr){
        int len = 0;
        int sum = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        
        for(int i=0;i<arr.length;i++){
            if(arr[i]>0)
                arr[i] = 1;
            if(arr[i]<0)
                arr[i] = -1;
        }
        
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
            if(!map.containsKey(sum))
                map.put(sum,i);
            if(map.containsKey(sum))
                len = Math.max(i - map.get(sum),len);
        }
        
        return len;
    }
}

发表于 2021-03-15 14:18:51 回复(0)

Java

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
       
         Map<Integer,Integer> map = new HashMap<>();
        //key为 正数个数-负数个数
        map.put(0,-1);
        int key = 0,maxLen = 0;
        for(int i=0;i<n;i++){
            key += arr[i]==0?0:arr[i]/Math.abs(arr[i]);
            
            if(map.containsKey(key)){
                maxLen = Math.max(maxLen,i-map.get(key));
            }else{
                map.put(key,i);
            }
            
        }
        
        System.out.print(maxLen);
		
	}
}

发表于 2019-10-24 13:08:04 回复(0)