2021-03-24:给定一个整数组成的无序数组arr,值可能正、可能负、可能0。给定一个整数值K,找到arr的所有子数组里,哪个子数组的累加和等于K,并且是长度最大的。返回其长度。
福大大 答案2021-03-24:
我刚开始的想法,是对数组的每一位加上一个值,把数组全部变成非负数。比如[-5,3,1]变成[0,8,6]。可惜这种方法行不通,因为整数值K会变成不固定,还是没法用双指针。
求前缀和,存map。
代码用golang编写,代码如下:
package main import "fmt" func main() { arr := []int{1, -1, 2, 3, -4, -1, 9} ret := maxLength(arr, 9) fmt.Println(ret) } func maxLength(arr []int, k 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++ { sum += arr[i] if _, ok := mmap[sum-k]; ok { llen = getMax(i-mmap[sum-k], 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 } }
执行结果如下: