未排序数组中累加和为给定值的最长子数组长度

[编程题]未排序数组中累加和为给定值的最长子数组长度

热度指数：8317 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度

输入描述:

第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

5 0
1 -2 1 1 1

输出

备注:

算法知识视频讲解

<云昊>

package main

import (
    "fmt"
)

func main() {
    var (
        n int 
        k int 
        num int
    )
    fmt.Scan(&n,&k)
    arr := make([]int,n)
    for i:=0;i<n;i++ {
        fmt.Scan(&num)
        arr[i] = num 
    }
    result := getMaxLength(arr,k)
    fmt.Printf("%d\n",result)
}

func getMaxLength(arr []int, k int) int {
    if len(arr) == 0 {
        return 0
    }
    length, sum := 0, 0
    m := make(map[int]int)
    //初始化位置
    m[0] = -1
    for i :=0;i<len(arr);i++ {
        sum += arr[i]
        if v,ok := m[sum-k];ok {
            length = max(length,i-v)
        }
        if _,ok := m[sum]; !ok {
            m[sum] = i 
        }
    }
    return length 
}

func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}

发表于 2021-11-14 15:17:37 回复(0)