2021-03-29：无序数组arr，子数组-1和1的数量一样多，请问最长子数组的长度是多少？
福大大 答案2021-03-29：
[1, -1, 2, 3, -4, -1, 9]变成[1, -1, 0, 0, 0, -1, 0]，累加和等于0的最长子数组长度，就是所需要的值。
求前缀和，存map。
代码用golang编写。代码如下：
package mainimport "fmt"func main() { arr := []int{1, -1, 2, 3, -4, -1, 9} ret := maxLength(arr) fmt.Println(ret)}func maxLength(arr []int) int { if len(arr) == 0 { return 0 } // key:前缀和 // value : 0~value这个前缀和是最早出现key这个值的 mmap := make(map[int]int) mmap[0] = -1 // important llen := 0 sum := 0 for i := 0; i < len(arr); i++ { if arr[i] ����,�亹== 1 { sum++ } else if arr[i] == -1 { sum-- } if _, ok := mmap[sum]; ok { llen = getMax(i-mmap[sum], llen) } if _, ok := mmap[sum]; !ok { mmap[sum] = i } } return llen}func getMax(a int, b int) int { if a > b { return a } else { return b }}执行结果如下：
评论