云社区 博客 博客详情

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

福大大架构师每日一题 发表于 2021-03-29 22:32:05 2021-03-29
0
0

【摘要】 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
    }
}

执行结果如下:
在这里插入图片描述


评论

登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:huaweicloud.bbs@huawei.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 0
点赞
分享文章到微博
分享文章到朋友圈

上一篇:2021-03-28:定义一种数:可以表示成若干(数量>1)连续正数和的数 。比如:5 = 2+3,5就是这样的数 ;12 =

下一篇:2021-03-30:给定一个整数组成的无序数组arr,值可能正、可能负、可能0。给定一个整数值K,找到arr的所有子数组里,哪

评论 (0)


登录后可评论,请 登录注册

评论