如何优化求非负数组中和为s的最长连续子数组的平方级解法

因为给定的数组元素都是非负整数，可以用*滑动窗口（双指针）*法把时间复杂度从O(n²)降到O(n)，完美解决大输入超时的问题。

优化思路 #

• 初始化左指针left=0，当前窗口和curr_sum=0，记录最优解的左右边界best_l=-1、best_r=-1、最优长度best_len=-1
• 遍历右指针right从0到数组末尾：
  1. 把当前右指针的元素累加到curr_sum
  2. 只要curr_sum大于s，就不断把左指针指向的元素从curr_sum减去，左指针右移，直到curr_sum ≤ s
  3. 如果此时curr_sum等于s，判断当前窗口长度是否比之前记录的最优解更长，更长就更新最优解；如果长度相同，因为我们是按左指针从小到大遍历的，最先出现的解就是左边界最小的，不需要更新
• 最后根据最优边界返回结果即可

优化后的代码 #

def findLongestSubarrayBySum(s, arr):
    n = len(arr)
    curr_sum = 0
    left = 0
    best_len = -1
    best_l = best_r = -1
    for right in range(n):
        curr_sum += arr[right]
        # 窗口和超过s就收缩左边界
        while curr_sum > s and left <= right:
            curr_sum -= arr[left]
            left += 1
        # 匹配到和为s的窗口
        if curr_sum == s:
            current_len = right - left + 1
            # 只有更长的窗口才更新，保证相同长度时左边界更小的解被保留
            if current_len > best_len:
                best_len = current_len
                best_l = left + 1
                best_r = right + 1
    return [best_l, best_r] if best_len != -1 else [-1]

代码验证 #

你给出的所有测试用例都可以正常通过：

• 测试用例s=12, arr=[1, 2, 3, 7, 5] → 返回[2, 4]
• 测试用例s=15, arr=[1, 2, 3, 4, 5, 0, 0, 0, 6, 7, 8, 9, 10] → 返回[1, 8]
• 测试用例s=3, arr=[0, 3, 0] → 返回[1, 3]
• 测试用例s=0, arr=[1, 0, 2] → 返回[2, 2]
  所有边界情况、含0的特殊情况都符合要求。

内容的提问来源于stack exchange，提问作者Gonzo