2021-03-29:无序数组arr,子数组-1和1的数量一样多,请问最长子数组的长度是多少?
16lz
2021-03-30
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人进行了赞赏支持
更多相关文章
- 前端技巧:遍历数组都有哪些方式呢?
- Ubuntu系统网络配置及shell脚本编程之函数数组等用法详解
- 串与数组,广义表
- C语言中的择中,二分查找算法解析
- C语言指针的理解
- 使用C语言判断密码是否正确,三次失败就退出,超详细教程!!
- python常用的图像处理工具有哪些?工具推荐!
- 零基础学习Java开发,这些学习笔记送给你
- Json序列化在golang中的应用