2021-03-24：给定一个整数组成的无序数组arr，值可能正、可能负、可能0。给定一个整数值K，

2021-03-24：给定一个整数组成的无序数组arr，值可能正、可能负、可能0。给定一个整数值K，找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的。返回其长度。

福大大答案2021-03-24：

我刚开始的想法，是对数组的每一位加上一个值，把数组全部变成非负数。比如[-5,3,1]变成[0,8,6]。可惜这种方法行不通，因为整数值K会变成不固定，还是没法用双指针。

求前缀和，存map。

代码用golang编写，代码如下：

package mainimport "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    }}

执行结果如下：

左神java代码
评论

你的鼓励让我更有动力

赞赏

0人进行了赞赏支持

你的鼓励让我更有动力

更多相关文章

随机推荐