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

福大大 答案2021-03-23:

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

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

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代码