数组元素全非负时，找和为k的连续子数组能否规避额外空间？

嘿，这个问题问得特别好！咱们来把这个事儿掰扯清楚——@talex说的没错，当数组元素全为非负时，确实存在不需要额外内存（除了几个变量）的更优算法，完全不需要哈希表或者集合，核心就是利用非负数组前缀和的单调性，用**滑动窗口（双指针）**来解决。

为什么滑动窗口可行？ #

因为数组里全是非负数，所以前缀和是严格非递减的——也就是说，当你扩大窗口（右移右指针）时，窗口内的和只会增加或不变；缩小窗口（右移左指针）时，和只会减少或不变。这种单调性让我们可以用两个指针动态调整窗口大小，而不需要记录所有历史前缀和。

具体思路 #

• 初始化两个指针left和right，都从数组起始位置开始
• 维护一个变量current_sum，记录当前窗口内元素的和
• 遍历数组，每次把右指针指向的元素加到current_sum中
• 当current_sum大于k时，尝试左移左指针，减去左指针指向的元素，直到current_sum小于k
• 每次当current_sum等于k时，就把计数加1（因为当前窗口就是一个符合条件的连续子数组）

举个例子验证（输入[1,1,1]，k=2） #

1. 初始left=0，right=0，current_sum=1，小于2，右移right到1
2. current_sum=1+1=2，等于k，计数加1（现在是1）
3. 因为current_sum不大于k，继续右移right到2，current_sum=2+1=3，大于k
4. 左移left到1，current_sum=3-1=2，等于k，计数加1（现在是2）
5. 遍历结束，最终计数就是2，和预期一致

代码示例（C++） #

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    long long current_sum = 0; // 用long long避免溢出
    int left = 0;
    
    for (int right = 0; right < nums.size(); ++right) {
        current_sum += nums[right];
        
        // 当当前和超过k时，缩小左边界
        while (current_sum > k && left <= right) {
            current_sum -= nums[left];
            left++;
        }
        
        // 找到符合条件的子数组
        if (current_sum == k) {
            count++;
        }
    }
    return count;
}

补充说明 #

可能你会疑惑，如果数组里有0怎么办？比如输入[0,0,0]，k=0——这个算法依然有效：每次右移右指针，current_sum保持0，每次都会触发计数加1，最终得到6，正好是所有连续子数组的数量（3*(3+1)/2=6），完全正确。

这个算法的时间复杂度是O(n)（每个元素最多被左右指针各访问一次），空间复杂度是O(1)，只用到了几个变量，完全不需要额外的哈希表或集合，这就是它比前缀和哈希表方法更优的地方。

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