前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >​2021-03-23:给定一个正整数组成的无序数组arr,给定一个正整数值K

​2021-03-23:给定一个正整数组成的无序数组arr,给定一个正整数值K

原创
作者头像
福大大架构师每日一题
修改2021-03-24 10:28:32
4310
修改2021-03-24 10:28:32
举报
文章被收录于专栏:福大大架构师每日一题

2021-03-23:给定一个正整数组成的无序数组arr,给定一个正整数值K,找到arr的所有子数组里,哪个子数组的累加和等于K并且是长度最大的。返回其长度。

福大大 答案2021-03-23:

双指针。小于等于K时,右指针右移,窗口和的值累加,等于时收集答案;大于K时,左指针右移,窗口和的值减少。

代码用golang编写,代码如下:

代码语言:txt
复制
package main

import "fmt"

func main() {
    arr := []int{1, 2, 3, 0}
    ret := getMaxLength(arr, 6)
    fmt.Println(ret)
}
func getMaxLength(arr []int, K int) int {
    arrLen := len(arr)
    if arrLen == 0 {
        return 0
    }
    ans := 0
    left := 0
    right := 0

    sum := arr[0]
    for right < arrLen-1 {
        if sum == K {
            ans = getMax(ans, right-left+1)
            right++
            sum += arr[right]
        } else if sum < K {
            right++
            sum += arr[right]
        } else {
            sum -= arr[left]
            left++
        }
    }

    if sum == K {
        ans = getMax(ans, right-left+1)
    }

    return ans
}

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

执行结果如下:

在这里插入图片描述
在这里插入图片描述

左神java代码

评论

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档