含正负值数组的最短和≥target子数组：前缀和+bisect解法解析

原LeetCode 209题（全正数组找最短子数组和≥target）可以用滑动窗口解决，但当数组包含正负值时，前缀和不再具备单调性，滑动窗口的逻辑直接失效。这时候可以用前缀和+二分查找的O(nlogn)解法，下面详细拆解核心逻辑：

核心目标转化 #

首先构造前缀和数组prefix，其中prefix[0] = 0，prefix[i]表示前i个元素的累加和（即prefix[i] = nums[0] + nums[1] + ... + nums[i-1]）。
子数组nums[j..i-1]的和等于prefix[i] - prefix[j]，我们要找的是最小的i-j，使得prefix[i] - prefix[j] ≥ target。
转化一下不等式：prefix[j] ≤ prefix[i] - target。也就是说，对每个i，我们需要找到最大的j < i，满足prefix[j] ≤ prefix[i] - target——这样i-j的长度才会尽可能小（因为j越大，长度越短）。

为什么需要sorted_prefix？ #

因为数组含正负值，prefix数组不再是单调递增的，直接对原prefix数组二分查找是行不通的。所以我们需要维护一个始终有序的前缀和列表：sorted_prefix，里面存储的是(前缀和值, 对应索引)的元组，且列表按前缀和值从小到大排序。这个有序列表就是二分查找的基础。

二分查找的具体逻辑 #

对每个i，计算target_prefix = prefix[i] - target，然后在sorted_prefix中查找最大的前缀和值≤target_prefix：

• 代码里用的是左闭右开区间的二分法：初始化left=0，right=len(sorted_prefix)
• 当中间位置的前缀和≤target_prefix时，说明当前位置符合条件，我们可以尝试找更靠右的符合条件的元素（因为要最大的j），所以left = mid + 1
• 否则，说明中间位置的元素太大，需要往左缩小范围，right = mid
• 循环结束后，left指向第一个大于target_prefix的元素索引，那么left-1就是最后一个符合条件的元素索引。如果left>0，说明存在这样的j，计算i-j并更新最小长度。

维护sorted_prefix的意义 #

每次处理完当前prefix[i]，用bisect.insort把(prefix[i], i)插入到sorted_prefix中——这个方法会自动保持列表的有序性。这样后续处理更大的i时，当前的prefix[i]就能作为候选的j被查找，保证所有之前的前缀和都能被考虑到。

示例代码 #

import bisect

def shortest_subarray_sum_at_least_k(nums, target):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    min_len = float('inf')
    sorted_prefix = []
    
    for i in range(n + 1):
        target_prefix = prefix[i] - target
        # 找到最大的j满足prefix[j] <= target_prefix
        left = 0
        right = len(sorted_prefix)
        while left < right:
            mid = (left + right) // 2
            if sorted_prefix[mid][0] <= target_prefix:
                left = mid + 1
            else:
                right = mid
        if left > 0:
            j = sorted_prefix[left - 1][1]
            min_len = min(min_len, i - j)
        # 将当前前缀和插入有序列表，维持排序状态
        bisect.insort(sorted_prefix, (prefix[i], i))
    
    return min_len if min_len != float('inf') else -1

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