数组与矩阵---未排序数组中累加和小于或等于给定值的最长子数组问题

【题目】

　　给定一个无序数组arr，其中元素可正、可负、可0，给定一个整数k。求arr所有的子数组中累加和小于或等于k的最长子数组长度。
　　
　　例如：arr = [3, -2, -4, 0, 6]，k = -2，相加和小于或等于-2的最长子数组为[3, -2, -4, 0]，所以结果返回4。

【基本思路】

　　方法一：时间复杂度O(NlogN)，空间复杂度O(N)。
　　
　　依次求以数组每个位置结尾的累加和小于或等于 k 的最长子数组长度。如何找呢？首先生成每个位置的累加和数组 sumArr，对于每一个位置 i，要求以该位置结尾的累加和小于或等于k的最长子数组，实际上只要找到 sumArr[0…i] 中第一个大于或等于sum-k的位置，假设位置为 index，那么 arr[index+1…i] 就是以 i 位置结尾的累加和小于或等于 k 的最长子数组。

　　那么如何快速的求出 sumArr[0…i] 中第一个大于或等于 sum-k 的位置呢？假设累加和数组sumArr = [0,1, 3, 2, 7, 5]。注意这里数组的第一项0表示没有任何一个数时的累加和，它的存在是为了防止以 0 位置开头的子数组的丢失（这个在未排序数组中累加和为给定值的最长子数组中已经分析过）。对于数组sumArr我们可以将它转变为 [0, 1, 3, 3, 7, 7]，为什么呢？因为我们只关心第一个大于 sum-k 的位置，如果累加和为 2 已经大于 sum-k，那么累加和 3 必定也大于 sum-k，所以只要保留一个更大的、出现更早的累加和就可以。转变后的数组很显然是一个有序数组，那么我们就可以使用二分查找在 logN 的时间复杂度内找到第一个大于或等于 sum-k 的位置。如果不转变成有序数组，很显然，我们需要用 N 的复杂度去遍历寻找满足条件的位置。

　　具体实现参见如下代码：

#python3.5
def maxLen(arr, k):
    def getLessIndex(h, num, index):
        left = 0
        right = index
        res = 1
        while left <= right:
            mid = (left + right) // 2
            if h[mid] >= num:
                res = mid
                right = mid - 1
            else:
                left = mid + 1
        return res

    if arr == None or len(arr) == 0:
        return 0
    sum = 0
    length = 0
    h = [0 for i in range(len(arr)+1)]
    for i in range(1, len(h)):
        sum += arr[i-1]
        h[i] = max(h[i-1], sum)
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]
        pre = getLessIndex(h, sum-k, i)  #这个位置是h中的下标，注意转换成arr中的下标
        tmpLen = 0 if pre == -1 else i-pre+1
        length = max(length, tmpLen)
    return length

　　方法二：时间复杂度O(N)，空间复杂度O(N)。

#python3.5
def maxLen2(arr, k):
    if arr == None or len(arr) == 0:
        return 0
    help = [0 for i in range(len(arr))]   #以i位置开头能达到的最小累加和
    help[-1] = arr[-1]
    map = {}   #以位置i开头的最小累加和数组的最右位置
    map[len(arr)-1] = len(arr) - 1
    for i in range(len(arr)-2, -1, -1):
        if help[i+1] <= 0:
            help[i] = help[i+1] + arr[i]
            map[i] = map[i+1]
        else:
            help[i] = arr[i]
            map[i] = i
    res = 0   #全局变量记录最大子数组长度
    end = 0   #子数组右边界的下一个位置
    sum = 0   #子数组累加和
    for i in range(len(arr)):
        #计算以i位置开头满足条件的最大子数组
        while end < len(arr) and sum + help[end] <= k:
            sum += help[end]
            end = map[end] + 1
        #更新最大子数组长度
        res = max(res, end - i)
        #子数组左边界向右移动一位
        sum -= arr[i] if end > i else 0
        #更新end
        end = end if end > i else i + 1
    return res