Meta 非负连续子数组存在性：零值与非空窗口

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入全非负，子数组必须非空；target<0直接false。出现负数时拒绝此实现，改用前缀和集合。
• 目标是存在性而非数量；计数版遇到零会有多个合法左端点，不能直接将此算法计数。

解题路线

1. 扩张右端把新值加总；只要sum>target就收缩左端。非负性保证收缩不会增大和，而后续扩张不会减小和。
2. 每轮收缩后sum<=target，若sum==target且left<=right就找到非空解。target=0时必须检查窗口非空，否则所有正数会被收缩成空窗口误判true。
3. 正数版唯一左端点性质不适用于含零数组，存在性仍正确；负数破坏单调性，例如[3,−2]目标1需要保留初始超目标值。

手动走一遍

[1,3,2,5,7,2]目标14存在[2,5,7]；[1]目标0没有解，[0]目标0有解，空数组目标0没有解。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def subarray_exists(values, target):
    """A nonempty contiguous subarray; nonnegative values only."""
    if any(v < 0 for v in values):
        raise ValueError("negative value invalidates the sliding-window contract")
    if target < 0:
        return False
    left = 0
    total = 0
    for right, value in enumerate(values):
        total += value
        while left <= right and total > target:
            total -= values[left]; left += 1
        if left <= right and total == target:
            return True
    return False

复杂度

O(n)时间，O(1)辅助空间；每元素至多进入和离开窗口一次。

易错点与追问

容易失分的边界

• 没有非负前提就使用双指针，会漏掉负数抵消形成的解。
• while结束后的sum=0可能来自空窗口；题目要求非空时不能接受。

继续深挖

• 允许任意整数，用先查prefix−target是否出现再加入当前prefix的集合方法，O(n)预期时间/O(n)空间。
• 若输出全部非负窗口，零可能使结果O(n²)；复杂度需包含输出大小。