2021-03-29:无序数组arr,子数组-1和1的数量一样多,请问最长子数组的长度是多少?
【摘要】 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...
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 main
import "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
}
}
执行结果如下:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)