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    }}

执行结果如下：

©著作权归作者所有：来自51CTO博客作者福大大的原创作品，如需转载，请注明出处，否则将追究法律责任

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

2021-03-29：无序数组arr，子数组-1和1的数量一样多，请问最长子数组的长度是多少？

每一份赞赏源于懂得

更多相关文章

随机推荐