前缀和算法_bcbcbcbccbcbcbcbcbcbcbcbcbcb

什么是前缀和

给定一个数组int[] ints，则其对应的前缀和数组为int[] sums 其中sums.length = ints.length + 1，sums[0]为0。
存在正整数n，满足0<n<sums.length,其中sums[n]表示数组中前n项和(n指的不是数组下标，是下标+1)。
suns[n]表示数组下标位置之前元素之和，所以就会有sums[i+1] = sums[i] + ints[i]
如存在数组int[] ints = {1,2,3,4}，则有int[] sums = {0,1,3,6,10}

前缀和算法

数组int[] ints，数组int[] sums = new int[ints.length + 1];

for(int i = 1;i < sums.length ; i++){
	sums[i] = sum[i - 1] + ints[i - 1]
}

1
2
3
4

所以计算数组下标区间i-j的元素之和就为 res = sums[j+1] - sums[i]。
sums[i]表示数组第i下标之前所有元素之和
sums[j+1]表示数组第j+1下标之前所有元素之和，sums[j]并没有计算ints[j]

前缀和算法应用

应用一

给定字符串长度为10000，字符串中只有ABC三种字符，如果字符串中ABC三种字符数目相等，这样的字符串就叫相等字符串，求字串的最长相等字符串长度

package org.algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Random;

/**
 * 给定字符串长度为10000，字符串中只有ABC三种字符，如果字符串中ABC三种字符数目相等，这样的字符串就叫相等字符串，求字串的最长相等字符串长度
 */
public class TestString {

    private static final int MEDIA = 65;// A 65 B 66 C 67
    private static final int MAX = 10000;// 字符串有多长
    private static final char[] CHARS = new char[MAX];// 字符串的数组长度

    static {
        Random random = new Random();
        for (int i = 0; i < CHARS.length; i++) {
            CHARS[i] = (char)(random.nextInt(3)+MEDIA);
        }

    }
    public static void main(String[] args){

        int[] preA = new int[CHARS.length+1];// preA[CHARS.length] 表示整个字符串中A的总数，preA[j+1] - preA[i]区间的插值表示i到j之间A的数量
        int[] preB = new int[CHARS.length+1];// preB[CHARS.length] 表示整个字符串中B的总数，preB[j+1] - preB[i]区间的插值表示i到j之间A的数量
        int[] preC = new int[CHARS.length+1];// preB[CHARS.length] 表示整个字符串中B的总数，preC[j+1] - preC[i]区间的插值表示i到j之间A的数量

        for (int i = 0; i < CHARS.length; i++) {
            switch (CHARS[i]) {
                case 'A' :
                    preA[i+1] = preA[i]+1;
                    preB[i+1] = preB[i];
                    preC[i+1] = preC[i];
                    break;
                case 'B' :
                    preA[i+1] = preA[i];
                    preB[i+1] = preB[i]+1;
                    preC[i+1] = preC[i];
                    break;
                case 'C' :
                    preA[i+1] = preA[i];
                    preB[i+1] = preB[i];
                    preC[i+1] = preC[i]+1;
                    break;
            }
        }
        System.out.println(new String(CHARS));
        /**
         * 在前缀和preA[],preB[],preC[]中,存在区间i-j直接存在preA[j+1] - preA[i] = preB[j+1] - preB[i] = preC[j+1] - preC[i] 则j-i就是子字符串最大长度
         * preA[j+1] preB[j+1] = preA[i] - preB[i] = x;
         * preA[j+1] preC[j+1] = preA[i] - preC[i] = y;
         * 只要从i=1，遍历到i=CHARS.length,map记录(Pair(x,y),i),出现相同情况，记录坐标差值，最大的插值就是子字符串的长度
         */
        Map<Pair,Integer> dic = new HashMap<>();
        // 不玩里面添加会漏掉['A','B','C']情况
        dic.put(new Pair(0,0),0);
        int res = -1;
        // 可以把这个for循环添加到上面的for中去
        for (int i = 1; i < CHARS.length; i++) {
            Pair pair = new Pair(preA[i] - preB[i], preA[i] - preC[i]);

            if (dic.containsKey(pair)){
                res = Math.max(i - dic.get(pair),res);
            }else {
               dic.put(pair,i);
            }

        }
        System.out.println(res);
    }

}

class Pair{
    int x;
    int y;
    public Pair(){}

    public Pair(int x,int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return x == pair.x && y == pair.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

字符串
CBCBACBCACCBCABCABCCBCBCACCCCCCAACBCCCABBCABAABACABCCCCBABABCCCCBCBCBAACBAAAACABACBCABABCABCBCAAACBBCCBBBCACCACACCAACBBBACCACABCCCBAAAACCBACAABACAAAAABBBBACABCBCBBBAABCCBBCBBAABACAABBCCCCCABCBBABABCBCCBAACBCBCBABABABCACABACCABBCAAABCCBBBCCAAACBCAACACABABBCACACACCCBCBABAACACCCCCAACBABBBACBAACBBBBABBBCAAABAACCCCBCCBCACACBACCABBCBCCACCAABCCAABBACBBCACAABCCCCAABABCCCABCCACBCAABAAACABBABCACCCABCBAAAACCACAABCCCBCACCBAABCBCAABCBABAAABBBACCAAACBBCBBBBCBACABCCCBABBBBBCBCBBBCBACCBAACAACBBACABACAAACCACBCBAACBBCAAACBABACAABBBBAACBACAACACBCAAABABBCBBCCBBAABCBCBBBCCCAAAAACAACCAAACBCBCACCACCACCCBCBBBBABCACBBBBCBABCCBBCAABCBACBBBBCCCCABCBAACBCACAAABCCBBBBBCCAAABABACBAAACCBBAABACCCBABABBABBCAACCBCCAABBBBBCABBBACABCAABBAABCABAACBBCABACBBBCCABCAAAACBBCACACBBCABCAACAAAABABBCAAAAAACBBAAAAABABBABBCBCBCCACCBBACACCCBCBBBCBBBACACACBBCAAABBABCACABBCCCCBCCABBCABAACBABBBAACACCBCBBACCBBCBBBCABABBCBCCCCCBCABAAACAABACACBACCCACCBCCAACAABCBCCABACBCBCCCCAACBBACCCCACBBCBCACABAAACBBBCBCAAAAACCBBABBAABAACBACAAAAAACBCACCCABACBCABABACBCBAACABCACBACCCAABCAABACCBBBBCCACBACCBABBCBAABBCABCBCBBCCBCACCCAABACCAAAACBCCABAACACCCABCBCABCBCAACACCCCAAACACBBCCAABACACBACCAABCBABAABAACBABABBABBCCBBBBBCBBBAAABBAACBBCBCCBCBACACBAAABBAACBBACCBBAACBAACBCCBBCCBBAACCACCBACABBBCBBABCACACBCBBBACBABABAACCCBCBCBBCACABBBACBBCCBCBCCACCBCCBABCCCBCAABACCBACBABBCBCAAAAABBCACACCCACBBACABACCAACBCCACCABABCBACBCBABACCBBCCABBCAAABBCCCBBACCCAACCCCACBBACABABBCBACBBAABCCBCCBACCBACBCBCCACBCBBCBBABBABABBAAABAAABACBCBCBACBBBCACBBBACCABACABACAABCCBBABCCAABBCABACABBACACCAABBBACCABACBABABAAABABACABABCCBBACBCBBBAACBCCAABAACABBCCCBCCCBCABABACBCCACBBCBABBCBBCCBCCACCAACCACAACBABBCCAACCCACCBCBCCABBCCCCBACBACABCBCBBCABACAABBABABBABCBBCACABCABCAAABCBCCCBCCABABAABBBBCBCBAACCBCCBACAACBCABACACAACBCAABBACCABBABABAACBABCBBACBAACCBACAACCCBCBCABCBBCBBBBBCABCAAACBCCCCABBAACACCBACCCAABABBACCBAABAABBBACCABBABACBBBBACBCCBCCABCBBCCABABBCCCCBCABCCBABACABBCCCACCAABBCAACCBAACBACBCCACBAAABBBBCACBCCAACACBBABCAACABAABCACCABABBCABAABCAABCCACACAABACACAACACAABCCAAAAACABABCAAAAAACBBBCBBABCCCAACBCCCAABBAABABCCCCCACAACCBBCAAACCBBBCAACABBBAABBBCBBACACAABABCABABAACAACAAAAACBCAABCBABBAABAABCBCCCABAAAAACBACAACCAACBCBBBBBCCBBBBBCAAABBBCCCABABBCBACABAABCABCABBCACAACBCAAACCACBABCCACCBBCBCAABBAABCCCBBBACABAACCABABBCBCBCAAABACABAACAAAACCBCCBCBBCABBCACAACABBCCBCACABCBCAABCABABCBCBACBAABABAAAAACCCBBACAAAAABBACBBACACCAAAACBABCABAABACCAABCCBAACBACACCBCABCAAAAACCBCBAAACCCACCCCBBCABBBACCACACBABABBCCAACBBBAACBCCACAAAABACCCAAAAACCABBACCCACABCCACBCCCCCCCCABBCBACCACAABBBCCAACBABBABCCBCACCCCBBBABCACBBCABBACBBABCACBCBCBACCBBCABCAACABCACABBBBAABCBCCCABAACAABCAABBACBBACAAABBBCCBABBCCCBCBBABBACAABABBCACCCBBCBBBCBABCBAAACCABABBACCBBBAABCCABABCABABAABACACBABBBABBBACAACABBBCABABCCABCBCACCCBABCABBBABABCBABCCBCCCBABBCAACAABAACCCCBCBCCACACCBBACBABBACBACCBCACCCCAAACBBABAABCBBBCCABBACABCCABAAAAABCAABCABBAABCABCCCACBAACCCCAAAABCBCCACCCAABCCBAACCCCBCACBCAABACBACBCCAABBCAACCBCABBCBACACBBCBCBBBCBBACCACBABBCBBCBACAABABABBACAAABCCCCBCBBBBABBACABCCAAABABBACBABCBABBAABAAABBACCABBCBACAAAAACCBCACBABBACBACACABABABAAACCCCCBCCAABBBABABABBCCCBBBBBBABACBAABCBCACAAAABACCABBBCACBAAAABCABBACCAABCCAABBACCBACCBCBABCBCCCBAACBBBABCACACABABBABBAAACABCAAAACBBCBAAACBAABCACCCCBBABABABAAABABCABBAACBCABBBBAABBBBBBACBABBBABBBBCBBCCCBBABBCCABBCBCBCACBBBCCBCABCBCAABACBBBBCBAAABACBACABCCBCACCCBCAACAACABCABCBACABBAABCABACBCBACCACACAACCCBCBBCACBBCCBACAAAABCACCAAABCCBCBCCBCCAACBCBBCACCBBCBCBCABBABBABBCBABBABBAABCBCCBCCABCCBABCBBCCACCBCBACBAAAACCBCCABABABCBBAAABCCBCAAACCCCBCCBBABCACBACCCACABCBCBABAABBBCBCAACACCCAABAACBABACBAABBBCAAAAACABBCCCBBACABBCCABCCBCABBACCBACBCCACBCBCAAACBACBBAACAACCCACCBCCCACACBCBCBCBACCBBCCBBABBCBBCAABAABABBABCCABBCCCACBABABBBAACAABBABCCACCAACBACABCCBAABACBBABABACAACCCBCCBCAABBBCACCCCABABBBCBACCABACAABAACBBABCBAABBABBAACBBAACCCBACCABCACABCCBBACCABCCCAAACCABCBBCBCACACCCACABAACAAACCCCBABBBCCBCBCCCCBBBCCBACACAAAABABCACCABBCBCAACAAACBBCCCAAABCBBABCBACCBCACACBAABACCBBAACCBCCACAACBCACBCCABCACACCBBBABCACCACABACABBBAACBCCCAAACBCCACABBCABAACACBBCABCBBAABAAAAABCAABCBCBABCABACABCAAAABBBABABCBCCACCCABAABBAAAACABBAABACAACBACABBBBCBACACACCCCCBABABBBCAACCCACCACABABCCCBBABAABACBACACAAACAACBACACCBCBACCACBBCACABACBCBCCACACCBCCCCCCCAACBACBCACBABBCACAAABCBABBBCBAAACACACCBCCBBAAACBBCABABABCAACBAACBCCCABCAACACABBAAAAABABCBCACACBAAAAAAAACCBAAABBCCABCBCACBCACBBBACABABABBAABBABBCAACABBCBBCABABACBBABABACABCCCBACCAABABABABACACACAABACCAABCCCABCABAACBABAACACACAAABBBBBACBCBAABABCBBABACABCBCCCCBCABBBCAABBCBABCCCACBCBCABACCCBACACBBCBBAACAACCCCBABABCCABACACCCBBBABBBBBACCBCCCBCAACAAACBAAAAABBBACABACAAACCABBBACBAABBAACCBCABBAAAAABCBBABCBABBBAACBBAACCBCCCBCBBCBACCBBCCBABCBABBBAACABBCCACBACABBCBCABABABBCBBBBAABACCCCACCACABCCABAAAAACBCBCAACCBACBBAAACACCCCAACABBCCCCAAACBCCCAABAABBBCCCBCCCABCABCABABABAABCABBCACCABCCAAACBBBBBCAACCBBACACCCCBCACBBBCCCBCCBBCAACCCBBCCCCBAACBAABBBACCCCBBCAACCABBCBBABAABCBACCABCCCAACCAACBCACCBBACBCAACBBAABBBBBCACBCABBABAAABACACCCBAABBCCBAAAABBABAABAACBABCACBABBBBCBBBABCBBBACAABCBCACAACAAAACCAABACBABCACAAACBCCCBCCCBBBCACCBBCCBCAACBAAAACABBBACCCAACBABCAAABACBAABBCACABBBAAACAAACCBCCAAABBBABCAAABCBCBCCAABCBBCAABBABBBACCACBBAAABAABABCCBABBBBAAABBACCABCCCAACBACACABBBACCACCCBBBAACCAAABCABBBCBBAAACBACABBCABBBAAACCCCCABCACBBACCCCCCCABAACACCCAABACCCABBCAACCBAAAAAABCACCCCBCCCBAACCAABBAABAACAABABABBBCCBBBBBBBCAABBCCACCBCCCBCABBBAABACBBBCBCCCCBACBCCBCBBBCBCBAACCBCBCCBAACBAABAACCBABCACBBCCAABBCCCCCBCABAAACBBBBCBBACBAAAACCBABCAABBAACCCBAABCCCBACABBAAAAACBBCCCCABCBACBAACBBAACBCBBCACCAABABBCACACACBABCCBAABABCBACBCCCBBACCBCABBABACAACAACBBCCBACBACACABCABBABCCACABCCABBAAABBBCBBBAAAABBBABCCCBAABBCAAABCCCBBBBAACACBAACABABCBACAABAAABBAABCABACCABABBCACBBBBBABACCCCBABBCABBBAAACAACCBBCCBBABCAAABBBABACCCCCACCCBBABBACBCBBBABAACBACBACBCBACCCACABCBCBAAABBCABCABBACABBCBACAACACCCCBBACCACACBBBCAACBABBCBCCCABCCABBABBABAACCBCAACBABAACBACBBBACACCBABACAAABBBAABCCAAACAAAAABABAAABABBACBCABAABABAABCCCBCCBBCAAABACBBCCBCACABACBAACCBCCCCCCBCBABBAACBCABCCBCCBBCBCBAABBCCCCAACAAACABCBCBBCBBBABABBACBBCCAACBACACACCACCCCABABACBBCABABAAACCCABCBAAAAACAAAABBACBCCAACBABAABABCCAACCBABCBACBBBCBBBBACCCBBBBBBCCCABBCAABCBBCCCACABCBBAACBBBBAACBCACABBBCBCCCACCCBCBBAAABACBACCCCABABAAAACACCABCCACCCABACBABABAABBABAACCCCCBCABBCBABAABCBABACBBBCAABABBABAABCAAACAAAACBACCCCBABAACABBBCBACCCCCBABAAAACAACCCAAACCAAAABCBABACCAABABBCACBBBBBCCABCBCBCBCBBAACBBABBACCCBAABABCBABACBBBAACACACCBBABBCBBABCCBCCCCCCAAABACABCBBBAACABBCACAAABBAACBACABBBAABAAABBABABAAABAAABCBBAABCBACBBBABCCBBBBAABABABAABBBACCCAACAAABCABCBBCCCABBACCAACCBBBABCBCBCCBBAAAACBCACACCBBABACCCBBCBCCBACCABCCCBBCCCCABBBACCCCCBACCCABAABCABCABBACCCAAAABBCCABACBCACBCCCBCACAABBCBAAABCBACBAACCBAAACABBCCCBCCABBABBBABBCBBBACCAACCCABAACCBBBAACAAAAABACBABABACCBBABCCCCCCCBABABABCAACCBBABAAACACCBACAABBABACAABBBCBABBCABCCAABCBCBAAACBBCBCBAACCBBACCBCABCCBBACAABBAABBBCBCCBABACAACABBBAACBCBBACABBBCAACABCCCABACABABCABCCACABBBACBACCCACBBCABBABCACBCCCCCCBCBCBBCCCCABCCBBAACABCBAAAABBABAAABCCBBCAABCBCAACACACABCABABCABCCACCCBACABBCAACACBACBBBCCCABACBCCBBCACABCCCCBBBCCAAABAABABBBBCACACABBACCCCABCCAAACBCABCACCACBABCCABCACACAACBCAABABABABAABABCCCACBCBABACCABCCBABCCABCAACBACABCBABCABAACCCAAACCCBBCCCCCCABABCCAABCCACAACCBCBBBCCAABBBCBCCABCBCCACCACCCCBACBACAACAACAACBCABBCACAAACBCCCACBABBCCBCBBCACCACCACBCBAAAACCCACCBBCCBCABBCCBCCBCACBBABCBCBAAACCBCBAAABBBABBCCCCCACBBCBAABCBCCBACACBACCBABBCBACABCCCCBCBAAABBACBBACACBABAACACBAACABBCBCCBBBAABBCCBAAACCACCCAACACCBBCBCBAAACCABCACACABBCCABAAABCCABABACAABBBAABCBCAABCCCBBBBACBBABBCBABAACABCBBBACAABBCBBCCCACBBBCBCCBACBABACAABBACABCAAAAABACCCBCABBBBABAAACACBBCBBCBCBAAABAAACBBAACCBBAABAACABCABCBBAACBACABABBBCBCBCBCCAAACBBCCBBBBBAAAABBCBCACCCCABCABBCBCCABBCBBABCBCACABBCCACCABAACCCACCABCABBBCBCACCCACABCCBAABBCBACCBACCBBACCCACBBAAAACAACCCBACCCAABCBBCAABCBBACAAABCBAABACCAACABBACAAACBCACBACACAABCBCCAABCCBBAABACAAABACAAABAAABBACCCABCCCCABCAABCBBCBAACACBCABCCBACACCABCBBBBBAABBBAACCABCBAABBACACBACCBBACBBBCABACBBBBACBAABCABCABCBCCBAAAABBCACCCCCACBACBCCCACBAABCACCCABACBAABCACAABAACCCCACCCCBACBBCACCBAAACACAABAABABCABBBCACCCBACCCCBBCBAACBACCCCCCCABCBBABCBCAAACABCBAAACACBBBCBBCBBBAACBBBBAAABCCACCAAAABCCCCBBABAABCCABCAAACCBBCCCACAACCBACBACCACBCCBABCABCACCCABCBBABCACCAACAABBCCCBBACBBCBCABCBBCBCCCBBACAAACBBBBCBAAACBCBCBBCBACAACABABCABABBBBCCBCBCBCBABACCBCBBBBCAACBBCCCBCAACCBACCBBCCCCBCCABCBCBACAABACBABABAACCBBACABAABCBABBACCBCAABBACACCBCCBAACCBBCAAABBACCBCAACBBABACBBABCCACCBABBBCCCBCBABBACACBCCABCBBCCCBCBBABAAACBBBABABBBABCAAACBCCABCAABCBBABBAAACBBACBBCAABBABCAABAAACBCBAAAAACABAACCCCBCCBCACBAABBCBAACACBCCCBBCAAABAACACAAAACBABACBABBAABAABBCAAAABCBAABABAABBCBCBACCBBAAAACCBBCBAABABAAACBCCACBCCCCAAACBCBCBBBBCCCCAABABBBABABBACAAAABBABBBCBBBACCCCCBBBCAAACBABCBACCCCABCCBACBBCCAAACBCACAAABBAACCACAABACCCABBCBBCBCAABBABBACAAABBCABAABAACBBABACCBCCACCCBCBBAAAABABACBAABBCBABBBCBACBBCABABBACAACBAABBBBCCBBBABBCAACCCCBBBABCBBABBBBBACBACBBABACCBCCACCCACBBBAACBCCACCABCACBBBAABACABBACACABBBCCBCACBBACBBCBBBABCACACCBAACCABABBBBBAABBBACAABCBCBAAAABCACBBCACCBCACBAAACBAACABBCCBCACCBBABBBBABACBABCBBAABBCAABBAAAAABBBAACCBBAAAAABBAACACCCBCCCABCCCBACABACCACBCACBBCCCCBCABABBCCBCCCACBBBAACCABABCBCCABBCABBBACCBCACACAABAAAABCACBACCABABAAACBBBBCBAACCCCAAAACCCCACABBBBBBABCBABACABBBCAACACCAAABCCACCCCCACCBACACCBACBCABBACCACCCCCBBAABABACBAACBABBBCBBCBCACBBCABCBCBBAAAAAACCBCAAACCABBBAACCABCBBACACCBBABBABBABABBAACCAABCCCBACABBBCBACBCCCCACCBCACBABCBCABCBCBABCAABCBBBACBCCABBCBBBBBBAABBCCBCABABBBABBCBBCCBAACBCCCACCCCAACCAAABCACBCABABACAACAACCBACBBAACACCCBAABCCBCCBBCABCBAAAABBABBAAAAABCACBBACABABBCABBBCBACCACABBBACCABCBCBAABCBCACBCAACABCABBBCBBAAABBBACCBCCBCBCCBCCACAACACACAABBBCABCCBACACAABCCACAACCCCCCACAABCABCBCBAAABCCAACBAACBBBBACBCACAABCBCCCABBBAABABBAACACBBBBCBCACBBABACBAAAACBBBBACABCCBBBAACCCABBBAACCCACCACCBCAABAACACCBAABABCCBBBABBAABCCCAACCABBBCBCCBCCCBCACBCBAAAAAAABBCAAABACCBCCABBAABBAABBBBBBCBCCBCBCBCBABACBBBBCBACBCACBCACABCBAABCABBBBCBACCCBBCBBAACACABAABACBBCBAABAABAABAAABBBBCCAABABBBCCCBAAACBACBBCAABAABCAACBCBAAAACCACCBABCAABBABABCABABBAACABACABABBCBABCAABBAAACCACBCCAABCBBAABCCBCBCACACBAAACCAAABCBBCBCBBAAABCBCCAABBACAAABCCACBBCACACCACBCCCCABBCACBACCCBBCCACBCBBBACCBBACBABACBBBCBCCCCBCBCAAAAAABACCCBBBCBBCCBBCBCABABCBCCABBBCCCCAAC
结果：9585
1
2
3

应用二

LeetCode17.05
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
解题思路：数组中只会出现两种情况，数字或者字母，先记录数组中出现数字的前缀和为preNums[]，数组中出现字母的前缀和为preStrs[],数组中要出现最长子数组区间i~j,则需要满足区间preNums[j+1] - preNums[i] = preStrs[j+1] - preStrs[i]。则：

preNums[j+1] - preStrs[j+1] = preNums[i] - preStrs[i]
preNums[j+1] + (-preStrs[j+1]) = preNums[i] + (-preStrs[i])

1
2
3

不如出现数字标记为1，出现字母标记为-1，则在字符数组中可出现以下替换
[“A”,“1”,“1”,A",“1”,“A”,“A”]
新数组[-1,1,1,-1,1,-1,-1] ints
前缀和[0,-1,0,1,0,1,0,-1] sums 记录没有出现的前缀和情况(hash记录前缀和,第一次出现的下标),第二次出现比较下标的长度是否和之前一样。

package org.algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Test {

    private static final String[] STR = new String[1000];

    static {
        Random random = new Random();
        StringBuilder str = new StringBuilder("[");
        for (int i = 0; i < STR.length; i++) {
            STR[i] = random.nextInt(2) == 0 ? "A" : "0";
            str.append(STR[i]).append(",");
        }
        System.out.println(str.substring(0,str.length()-1)+"]");
        String[] longestSubarray = findLongestSubarray(STR);
        StringBuilder stringBuilder = new StringBuilder("[");
        for (int i = 0; i < longestSubarray.length; i++) {
            stringBuilder.append(longestSubarray[i]).append(",");
        }
        System.out.println(stringBuilder.substring(0,stringBuilder.length() - 1) + "]");
        System.out.println(longestSubarray.length);
    }

    // 48 0 57 9
    public static void main(String[] args) {
        
    }

    public static String[] findLongestSubarray(String[] array) {

        Map<Integer,Integer> map = new HashMap<>();
        int res = 0;
        int sum = 0;
        int left = 0;
        int right = 0;
        map.put(0,-1);
        // 如果先计算好前缀和数组arraySums[array.length + 1]，从i = 1开始遍历数组，则需要在map中添加(0,0)，避免["A","1"]情况无法正确响应；
        // 由于这里从i = 0开始遍历所以数组，则map中添加为(0,-1)
        for (int i = 0; i < array.length; i++) {
            if (array[i].charAt(0) >= '0' && array[i].charAt(0) <= '9'){
                sum++;
            }else {
                sum--;
            }
            if (map.containsKey(sum)){
                if (res < i - map.get(sum)){
                    res = i - map.get(sum);
                    left = map.get(sum);
                    right = i;
                }
            }else {
                map.put(sum,i);
            }
        }
        if (right - left == array.length) return array;

        String[] result = new String[right - left];
        int index = 0;
        for (int i = left+1; i <= right; i++) {
            result[index] = array[i];
            index++;
        }

        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71