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 } }
执行结果如下: