给定一个整数组成的无序数组arr,值可能正、可能负、可能0。给定一个整数值K,找到arr的所有子数组里,哪个子数组的累加和<=K,并且是长度最大的。返回其长度。
1.前缀和+有序表。时间复杂度O(N*lgN)。无代码。
2.滑动窗口。时间复杂度O(N)。这道题用自然智慧想不到,需要练敏感度。有代码。 minSum数组,最小累加和,以i开头最小值。 minSumEnd数组,以i开头最小值,右边界在哪里。 采用滑动窗口,右指针每次移动多位,左指针每次移动一位。 虽然用到了两个for循环,但是右指针不回退,所以复杂度是O(N)。
代码用golang编写,代码如下:
package main
import "fmt"
func main() {
arr := []int{1000, -10, 60, -60, 3, 1, -2, 1, 10}
k := 1
ret := maxLengthAwesome(arr, k)
fmt.Println(ret)
}
func maxLengthAwesome(arr []int, k int) int {
if len(arr) == 0 {
return 0
}
minSums := make([]int, len(arr))
minSumEnds := make([]int, len(arr))
minSums[len(arr)-1] = arr[len(arr)-1]
minSumEnds[len(arr)-1] = len(arr) - 1
for i := len(arr) - 2; i >= 0; i-- {
if minSums[i+1] < 0 {
minSums[i] = arr[i] + minSums[i+1]
minSumEnds[i] = minSumEnds[i+1]
} else {
minSums[i] = arr[i]
minSumEnds[i] = i
}
}
// 迟迟扩不进来那一块儿的开头位置
end := 0
sum := 0
ans := 0
for i := 0; i < len(arr); i++ {
// while循环结束之后:
// 1) 如果以i开头的情况下,累加和<=k的最长子数组是arr[i..end-1],看看这个子数组长度能不能更新res;
// 2) 如果以i开头的情况下,累加和<=k的最长子数组比arr[i..end-1]短,更新还是不更新res都不会影响最终结果;
for end < len(arr) && sum+minSums[end] <= k {
sum += minSums[end]
end = minSumEnds[end] + 1
}
ans = getMax(ans, end-i)
if end > i { // 还有窗口,哪怕窗口没有数字 [i~end) [4,4)
sum -= arr[i]
} else { // i == end, 即将 i++, i > end, 此时窗口概念维持不住了,所以end跟着i一起走
end = i + 1
}
}
return ans
}
func maxLength(arr []int, k int) int {
h := make([]int, len(arr)+1)
sum := 0
h[0] = sum
for i := 0; i != len(arr); i++ {
sum += arr[i]
h[i+1] = getMax(sum, h[i])
}
sum = 0
res := 0
pre := 0
llen := 0
for i := 0; i != len(arr); i++ {
sum += arr[i]
pre = getLessIndex(h, sum-k)
if pre != -1 {
llen = i - pre + 1
}
res = getMax(res, llen)
}
return res
}
func getLessIndex(arr []int, num int) int {
low := 0
high := len(arr) - 1
mid := 0
res := -1
for low <= high {
mid = (low + high) / 2
if arr[mid] >= num {
res = mid
high = mid - 1
} else {
low = mid + 1
}
}
return res
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下: