2021-03-30：给定一个整数组成的无序数组arr，值可能正、可能负、可能0。给定一个整数值K，

2021-03-30：给定一个整数组成的无序数组arr，值可能正、可能负、可能0。给定一个整数值K，找到arr的所有子数组里，哪个子数组的累加和<=K，并且是长度最大的。返回其长度。

福大大答案2021-03-30：

1.前缀和+有序表。时间复杂度O(N*lgN)。无代码。

2.滑动窗口。时间复杂度O(N)。这道题用自然智慧想不到，需要练敏感度。有代码。
minSum数组，最小累加和，以i开头最小值。
minSumEnd数组，以i开头最小值，右边界在哪里。
采用滑动窗口，右指针每次移动多位，左指针每次移动一位。
虽然用到了两个for循环，但是右指针不回退，所以复杂度是O(N)。

代码用golang编写，代码如下：

package mainimport "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    }}

执行结果如下：

左神java代码
评论

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

每一份赞赏源于懂得

更多相关文章

随机推荐