什么是前缀和

给定一个数组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] } 

所以计算数组下标区间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); } } 

字符串 CBCBACBCACCBCABCABCCBCBCACCCCCCAACBCCCABBCABAABACABCCCCBABABCCCCBCBCBAACBAAAACABACBCABABCABCBCAAACBBCCBBBCACCACACCAACBBBACCACABCCCBAAAACCBACAABACAAAAABBBBACABCBCBBBAABCCBBCBBAABACAABBCCCCCABCBBABABCBCCBAACBCBCBABABABCACABACCABBCAAABCCBBBCCAAACBCAACACABABBCACACACCCBCBABAACACCCCCAACBABBBACBAACBBBBABBBCAAABAACCCCBCCBCACACBACCABBCBCCACCAABCCAABBACBBCACAABCCCCAABABCCCABCCACBCAABAAACABBABCACCCABCBAAAACCACAABCCCBCACCBAABCBCAABCBABAAABBBACCAAACBBCBBBBCBACABCCCBABBBBBCBCBBBCBACCBAACAACBBACABACAAACCACBCBAACBBCAAACBABACAABBBBAACBACAACACBCAAABABBCBBCCBBAABCBCBBBCCCAAAAACAACCAAACBCBCACCACCACCCBCBBBBABCACBBBBCBABCCBBCAABCBACBBBBCCCCABCBAACBCACAAABCCBBBBBCCAAABABACBAAACCBBAABACCCBABABBABBCAACCBCCAABBBBBCABBBACABCAABBAABCABAACBBCABACBBBCCABCAAAACBBCACACBBCABCAACAAAABABBCAAAAAACBBAAAAABABBABBCBCBCCACCBBACACCCBCBBBCBBBACACACBBCAAABBABCACABBCCCCBCCABBCABAACBABBBAACACCBCBBACCBBCBBBCABABBCBCCCCCBCABAAACAABACACBACCCACCBCCAACAABCBCCABACBCBCCCCAACBBACCCCACBBCBCACABAAACBBBCBCAAAAACCBBABBAABAACBACAAAAAACBCACCCABACBCABABACBCBAACABCACBACCCAABCAABACCBBBBCCACBACCBABBCBAABBCABCBCBBCCBCACCCAABACCAAAACBCCABAACACCCABCBCABCBCAACACCCCAAACACBBCCAABACACBACCAABCBABAABAACBABABBABBCCBBBBBCBBBAAABBAACBBCBCCBCBACACBAAABBAACBBACCBBAACBAACBCCBBCCBBAACCACCBACABBBCBBABCACACBCBBBACBABABAACCCBCBCBBCACABBBACBBCCBCBCCACCBCCBABCCCBCAABACCBACBABBCBCAAAAABBCACACCCACBBACABACCAACBCCACCABABCBACBCBABACCBBCCABBCAAABBCCCBBACCCAACCCCACBBACABABBCBACBBAABCCBCCBACCBACBCBCCACBCBBCBBABBABABBAAABAAABACBCBCBACBBBCACBBBACCABACABACAABCCBBABCCAABBCABACABBACACCAABBBACCABACBABABAAABABACABABCCBBACBCBBBAACBCCAABAACABBCCCBCCCBCABABACBCCACBBCBABBCBBCCBCCACCAACCACAACBABBCCAACCCACCBCBCCABBCCCCBACBACABCBCBBCABACAABBABABBABCBBCACABCABCAAABCBCCCBCCABABAABBBBCBCBAACCBCCBACAACBCABACACAACBCAABBACCABBABABAACBABCBBACBAACCBACAACCCBCBCABCBBCBBBBBCABCAAACBCCCCABBAACACCBACCCAABABBACCBAABAABBBACCABBABACBBBBACBCCBCCABCBBCCABABBCCCCBCABCCBABACABBCCCACCAABBCAACCBAACBACBCCACBAAABBBBCACBCCAACACBBABCAACABAABCACCABABBCABAABCAABCCACACAABACACAACACAABCCAAAAACABABCAAAAAACBBBCBBABCCCAACBCCCAABBAABABCCCCCACAACCBBCAAACCBBBCAACABBBAABBBCBBACACAABABCABABAACAACAAAAACBCAABCBABBAABAABCBCCCABAAAAACBACAACCAACBCBBBBBCCBBBBBCAAABBBCCCABABBCBACABAABCABCABBCACAACBCAAACCACBABCCACCBBCBCAABBAABCCCBBBACABAACCABABBCBCBCAAABACABAACAAAACCBCCBCBBCABBCACAACABBCCBCACABCBCAABCABABCBCBACBAABABAAAAACCCBBACAAAAABBACBBACACCAAAACBABCABAABACCAABCCBAACBACACCBCABCAAAAACCBCBAAACCCACCCCBBCABBBACCACACBABABBCCAACBBBAACBCCACAAAABACCCAAAAACCABBACCCACABCCACBCCCCCCCCABBCBACCACAABBBCCAACBABBABCCBCACCCCBBBABCACBBCABBACBBABCACBCBCBACCBBCABCAACABCACABBBBAABCBCCCABAACAABCAABBACBBACAAABBBCCBABBCCCBCBBABBACAABABBCACCCBBCBBBCBABCBAAACCABABBACCBBBAABCCABABCABABAABACACBABBBABBBACAACABBBCABABCCABCBCACCCBABCABBBABABCBABCCBCCCBABBCAACAABAACCCCBCBCCACACCBBACBABBACBACCBCACCCCAAACBBABAABCBBBCCABBACABCCABAAAAABCAABCABBAABCABCCCACBAACCCCAAAABCBCCACCCAABCCBAACCCCBCACBCAABACBACBCCAABBCAACCBCABBCBACACBBCBCBBBCBBACCACBABBCBBCBACAABABABBACAAABCCCCBCBBBBABBACABCCAAABABBACBABCBABBAABAAABBACCABBCBACAAAAACCBCACBABBACBACACABABABAAACCCCCBCCAABBBABABABBCCCBBBBBBABACBAABCBCACAAAABACCABBBCACBAAAABCABBACCAABCCAABBACCBACCBCBABCBCCCBAACBBBABCACACABABBABBAAACABCAAAACBBCBAAACBAABCACCCCBBABABABAAABABCABBAACBCABBBBAABBBBBBACBABBBABBBBCBBCCCBBABBCCABBCBCBCACBBBCCBCABCBCAABACBBBBCBAAABACBACABCCBCACCCBCAACAACABCABCBACABBAABCABACBCBACCACACAACCCBCBBCACBBCCBACAAAABCACCAAABCCBCBCCBCCAACBCBBCACCBBCBCBCABBABBABBCBABBABBAABCBCCBCCABCCBABCBBCCACCBCBACBAAAACCBCCABABABCBBAAABCCBCAAACCCCBCCBBABCACBACCCACABCBCBABAABBBCBCAACACCCAABAACBABACBAABBBCAAAAACABBCCCBBACABBCCABCCBCABBACCBACBCCACBCBCAAACBACBBAACAACCCACCBCCCACACBCBCBCBACCBBCCBBABBCBBCAABAABABBABCCABBCCCACBABABBBAACAABBABCCACCAACBACABCCBAABACBBABABACAACCCBCCBCAABBBCACCCCABABBBCBACCABACAABAACBBABCBAABBABBAACBBAACCCBACCABCACABCCBBACCABCCCAAACCABCBBCBCACACCCACABAACAAACCCCBABBBCCBCBCCCCBBBCCBACACAAAABABCACCABBCBCAACAAACBBCCCAAABCBBABCBACCBCACACBAABACCBBAACCBCCACAACBCACBCCABCACACCBBBABCACCACABACABBBAACBCCCAAACBCCACABBCABAACACBBCABCBBAABAAAAABCAABCBCBABCABACABCAAAABBBABABCBCCACCCABAABBAAAACABBAABACAACBACABBBBCBACACACCCCCBABABBBCAACCCACCACABABCCCBBABAABACBACACAAACAACBACACCBCBACCACBBCACABACBCBCCACACCBCCCCCCCAACBACBCACBABBCACAAABCBABBBCBAAACACACCBCCBBAAACBBCABABABCAACBAACBCCCABCAACACABBAAAAABABCBCACACBAAAAAAAACCBAAABBCCABCBCACBCACBBBACABABABBAABBABBCAACABBCBBCABABACBBABABACABCCCBACCAABABABABACACACAABACCAABCCCABCABAACBABAACACACAAABBBBBACBCBAABABCBBABACABCBCCCCBCABBBCAABBCBABCCCACBCBCABACCCBACACBBCBBAACAACCCCBABABCCABACACCCBBBABBBBBACCBCCCBCAACAAACBAAAAABBBACABACAAACCABBBACBAABBAACCBCABBAAAAABCBBABCBABBBAACBBAACCBCCCBCBBCBACCBBCCBABCBABBBAACABBCCACBACABBCBCABABABBCBBBBAABACCCCACCACABCCABAAAAACBCBCAACCBACBBAAACACCCCAACABBCCCCAAACBCCCAABAABBBCCCBCCCABCABCABABABAABCABBCACCABCCAAACBBBBBCAACCBBACACCCCBCACBBBCCCBCCBBCAACCCBBCCCCBAACBAABBBACCCCBBCAACCABBCBBABAABCBACCABCCCAACCAACBCACCBBACBCAACBBAABBBBBCACBCABBABAAABACACCCBAABBCCBAAAABBABAABAACBABCACBABBBBCBBBABCBBBACAABCBCACAACAAAACCAABACBABCACAAACBCCCBCCCBBBCACCBBCCBCAACBAAAACABBBACCCAACBABCAAABACBAABBCACABBBAAACAAACCBCCAAABBBABCAAABCBCBCCAABCBBCAABBABBBACCACBBAAABAABABCCBABBBBAAABBACCABCCCAACBACACABBBACCACCCBBBAACCAAABCABBBCBBAAACBACABBCABBBAAACCCCCABCACBBACCCCCCCABAACACCCAABACCCABBCAACCBAAAAAABCACCCCBCCCBAACCAABBAABAACAABABABBBCCBBBBBBBCAABBCCACCBCCCBCABBBAABACBBBCBCCCCBACBCCBCBBBCBCBAACCBCBCCBAACBAABAACCBABCACBBCCAABBCCCCCBCABAAACBBBBCBBACBAAAACCBABCAABBAACCCBAABCCCBACABBAAAAACBBCCCCABCBACBAACBBAACBCBBCACCAABABBCACACACBABCCBAABABCBACBCCCBBACCBCABBABACAACAACBBCCBACBACACABCABBABCCACABCCABBAAABBBCBBBAAAABBBABCCCBAABBCAAABCCCBBBBAACACBAACABABCBACAABAAABBAABCABACCABABBCACBBBBBABACCCCBABBCABBBAAACAACCBBCCBBABCAAABBBABACCCCCACCCBBABBACBCBBBABAACBACBACBCBACCCACABCBCBAAABBCABCABBACABBCBACAACACCCCBBACCACACBBBCAACBABBCBCCCABCCABBABBABAACCBCAACBABAACBACBBBACACCBABACAAABBBAABCCAAACAAAAABABAAABABBACBCABAABABAABCCCBCCBBCAAABACBBCCBCACABACBAACCBCCCCCCBCBABBAACBCABCCBCCBBCBCBAABBCCCCAACAAACABCBCBBCBBBABABBACBBCCAACBACACACCACCCCABABACBBCABABAAACCCABCBAAAAACAAAABBACBCCAACBABAABABCCAACCBABCBACBBBCBBBBACCCBBBBBBCCCABBCAABCBBCCCACABCBBAACBBBBAACBCACABBBCBCCCACCCBCBBAAABACBACCCCABABAAAACACCABCCACCCABACBABABAABBABAACCCCCBCABBCBABAABCBABACBBBCAABABBABAABCAAACAAAACBACCCCBABAACABBBCBACCCCCBABAAAACAACCCAAACCAAAABCBABACCAABABBCACBBBBBCCABCBCBCBCBBAACBBABBACCCBAABABCBABACBBBAACACACCBBABBCBBABCCBCCCCCCAAABACABCBBBAACABBCACAAABBAACBACABBBAABAAABBABABAAABAAABCBBAABCBACBBBABCCBBBBAABABABAABBBACCCAACAAABCABCBBCCCABBACCAACCBBBABCBCBCCBBAAAACBCACACCBBABACCCBBCBCCBACCABCCCBBCCCCABBBACCCCCBACCCABAABCABCABBACCCAAAABBCCABACBCACBCCCBCACAABBCBAAABCBACBAACCBAAACABBCCCBCCABBABBBABBCBBBACCAACCCABAACCBBBAACAAAAABACBABABACCBBABCCCCCCCBABABABCAACCBBABAAACACCBACAABBABACAABBBCBABBCABCCAABCBCBAAACBBCBCBAACCBBACCBCABCCBBACAABBAABBBCBCCBABACAACABBBAACBCBBACABBBCAACABCCCABACABABCABCCACABBBACBACCCACBBCABBABCACBCCCCCCBCBCBBCCCCABCCBBAACABCBAAAABBABAAABCCBBCAABCBCAACACACABCABABCABCCACCCBACABBCAACACBACBBBCCCABACBCCBBCACABCCCCBBBCCAAABAABABBBBCACACABBACCCCABCCAAACBCABCACCACBABCCABCACACAACBCAABABABABAABABCCCACBCBABACCABCCBABCCABCAACBACABCBABCABAACCCAAACCCBBCCCCCCABABCCAABCCACAACCBCBBBCCAABBBCBCCABCBCCACCACCCCBACBACAACAACAACBCABBCACAAACBCCCACBABBCCBCBBCACCACCACBCBAAAACCCACCBBCCBCABBCCBCCBCACBBABCBCBAAACCBCBAAABBBABBCCCCCACBBCBAABCBCCBACACBACCBABBCBACABCCCCBCBAAABBACBBACACBABAACACBAACABBCBCCBBBAABBCCBAAACCACCCAACACCBBCBCBAAACCABCACACABBCCABAAABCCABABACAABBBAABCBCAABCCCBBBBACBBABBCBABAACABCBBBACAABBCBBCCCACBBBCBCCBACBABACAABBACABCAAAAABACCCBCABBBBABAAACACBBCBBCBCBAAABAAACBBAACCBBAABAACABCABCBBAACBACABABBBCBCBCBCCAAACBBCCBBBBBAAAABBCBCACCCCABCABBCBCCABBCBBABCBCACABBCCACCABAACCCACCABCABBBCBCACCCACABCCBAABBCBACCBACCBBACCCACBBAAAACAACCCBACCCAABCBBCAABCBBACAAABCBAABACCAACABBACAAACBCACBACACAABCBCCAABCCBBAABACAAABACAAABAAABBACCCABCCCCABCAABCBBCBAACACBCABCCBACACCABCBBBBBAABBBAACCABCBAABBACACBACCBBACBBBCABACBBBBACBAABCABCABCBCCBAAAABBCACCCCCACBACBCCCACBAABCACCCABACBAABCACAABAACCCCACCCCBACBBCACCBAAACACAABAABABCABBBCACCCBACCCCBBCBAACBACCCCCCCABCBBABCBCAAACABCBAAACACBBBCBBCBBBAACBBBBAAABCCACCAAAABCCCCBBABAABCCABCAAACCBBCCCACAACCBACBACCACBCCBABCABCACCCABCBBABCACCAACAABBCCCBBACBBCBCABCBBCBCCCBBACAAACBBBBCBAAACBCBCBBCBACAACABABCABABBBBCCBCBCBCBABACCBCBBBBCAACBBCCCBCAACCBACCBBCCCCBCCABCBCBACAABACBABABAACCBBACABAABCBABBACCBCAABBACACCBCCBAACCBBCAAABBACCBCAACBBABACBBABCCACCBABBBCCCBCBABBACACBCCABCBBCCCBCBBABAAACBBBABABBBABCAAACBCCABCAABCBBABBAAACBBACBBCAABBABCAABAAACBCBAAAAACABAACCCCBCCBCACBAABBCBAACACBCCCBBCAAABAACACAAAACBABACBABBAABAABBCAAAABCBAABABAABBCBCBACCBBAAAACCBBCBAABABAAACBCCACBCCCCAAACBCBCBBBBCCCCAABABBBABABBACAAAABBABBBCBBBACCCCCBBBCAAACBABCBACCCCABCCBACBBCCAAACBCACAAABBAACCACAABACCCABBCBBCBCAABBABBACAAABBCABAABAACBBABACCBCCACCCBCBBAAAABABACBAABBCBABBBCBACBBCABABBACAACBAABBBBCCBBBABBCAACCCCBBBABCBBABBBBBACBACBBABACCBCCACCCACBBBAACBCCACCABCACBBBAABACABBACACABBBCCBCACBBACBBCBBBABCACACCBAACCABABBBBBAABBBACAABCBCBAAAABCACBBCACCBCACBAAACBAACABBCCBCACCBBABBBBABACBABCBBAABBCAABBAAAAABBBAACCBBAAAAABBAACACCCBCCCABCCCBACABACCACBCACBBCCCCBCABABBCCBCCCACBBBAACCABABCBCCABBCABBBACCBCACACAABAAAABCACBACCABABAAACBBBBCBAACCCCAAAACCCCACABBBBBBABCBABACABBBCAACACCAAABCCACCCCCACCBACACCBACBCABBACCACCCCCBBAABABACBAACBABBBCBBCBCACBBCABCBCBBAAAAAACCBCAAACCABBBAACCABCBBACACCBBABBABBABABBAACCAABCCCBACABBBCBACBCCCCACCBCACBABCBCABCBCBABCAABCBBBACBCCABBCBBBBBBAABBCCBCABABBBABBCBBCCBAACBCCCACCCCAACCAAABCACBCABABACAACAACCBACBBAACACCCBAABCCBCCBBCABCBAAAABBABBAAAAABCACBBACABABBCABBBCBACCACABBBACCABCBCBAABCBCACBCAACABCABBBCBBAAABBBACCBCCBCBCCBCCACAACACACAABBBCABCCBACACAABCCACAACCCCCCACAABCABCBCBAAABCCAACBAACBBBBACBCACAABCBCCCABBBAABABBAACACBBBBCBCACBBABACBAAAACBBBBACABCCBBBAACCCABBBAACCCACCACCBCAABAACACCBAABABCCBBBABBAABCCCAACCABBBCBCCBCCCBCACBCBAAAAAAABBCAAABACCBCCABBAABBAABBBBBBCBCCBCBCBCBABACBBBBCBACBCACBCACABCBAABCABBBBCBACCCBBCBBAACACABAABACBBCBAABAABAABAAABBBBCCAABABBBCCCBAAACBACBBCAABAABCAACBCBAAAACCACCBABCAABBABABCABABBAACABACABABBCBABCAABBAAACCACBCCAABCBBAABCCBCBCACACBAAACCAAABCBBCBCBBAAABCBCCAABBACAAABCCACBBCACACCACBCCCCABBCACBACCCBBCCACBCBBBACCBBACBABACBBBCBCCCCBCBCAAAAAABACCCBBBCBBCCBBCBCABABCBCCABBBCCCCAAC 结果：9585 

应用二

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，出现字母标记为-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; } }