猿辅导2017校园招聘笔试题 求和为0的最长连续子数组

数组"/>

猿辅导2017校园招聘笔试题 求和为0的最长连续子数组

题意：给定一个数组，数组中元素的值只能是1或者-1，求其和为0的最长连续子序列的长度；

数组为1，-1，1，-1，1，-1，1，-1，其结果为：8

数组为1，1，-1，1，1，-1，-1，其结果为：6

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;/*** dp[i] = arr[0] + arr[1] + ... + arr[i]* 如果 sum(arr[m]...arr[n]) = 0;* 那么 sum(arr[0]...arr[m-1]) = sum(arr[0]...arr[n])* 和为0的最长子序列: maxLen = n - m + 1, (dp[n] = dp[m-1])*/
public class Main {public static void main(String[] arg) {Scanner scan = new Scanner(System.in);while (scan.hasNext()) {int n = scan.nextInt();int[] numbers = new int[n];for (int i = 0; i < n; i++) {numbers[i] = scan.nextInt();}System.out.println(solve(numbers, n));}scan.close();}private static int solve(int[] numbers, int n) {int[] dp = new int[n];dp[0] = numbers[0];for (int i = 1; i < n; i++) {dp[i] = dp[i - 1] + numbers[i];}Map<Integer, Integer> dpMap = new HashMap<>();dpMap.put(0, 0);int maxLen = 0;for (int i = 0; i < n; i++) {if (!dpMap.containsKey(dp[i])) {dpMap.put(dp[i], i + 1);} else {int len = i - dpMap.get(dp[i]) + 1;maxLen = maxLen < len ? len : maxLen;}}return maxLen;}}