求正整数数组中和为S的连续子数组优化代码（返回最左索引）

问题回顾 #

给定一个大小为N的未排序正整数数组A，找到和为给定值S的连续子数组，返回其1-based的左右索引；若存在多个符合条件的子数组，返回从左到右最先出现的；若不存在则返回仅含-1的数组。

示例1：
输入：N=5，S=12，A[]={1,2,3,7,5}
输出：2 4
解释：第2到第4位元素的和为12。

示例2：
输入：N=10，S=15，A[]={1,2,3,4,5,6,7,8,9,10}
输出：1 5
解释：第1到第5位元素的和为15。

现有代码的问题分析 #

你提供的代码存在以下问题：

• 初始计算sum(A)带来额外O(n)开销，且无必要，遍历过程中即可判断是否存在解。
• 收集所有符合条件的子数组再筛选“最先出现”的逻辑冗余，题目要求的最先出现即左索引最小的解，找到后可直接返回，无需后续遍历。
• 最后筛选解的逻辑存在bug：flag被赋值为子数组列表而非索引，导致l[flag]会触发索引错误。
• 时间复杂度为O(n²)，面对大规模数组时效率低下。

优化方案：滑动窗口（双指针）解法 #

由于数组元素均为正整数，滑动窗口是最优解法：通过左右指针维护一个窗口，动态调整窗口大小来匹配目标和，时间复杂度可降至O(n)，空间复杂度O(1)。

优化后代码 #

def subArraySum(self, A, n, s):
    current_sum = 0
    left = 0
    
    for right in range(n):
        current_sum += A[right]
        
        # 当当前和超过目标值时，移动左指针缩小窗口
        while current_sum > s and left <= right:
            current_sum -= A[left]
            left += 1
        
        # 找到符合条件的子数组，立即返回1-based索引
        if current_sum == s:
            return [left + 1, right + 1]
    
    # 遍历结束未找到符合条件的子数组
    return [-1]

代码说明 #

1. 窗口维护：右指针逐步遍历数组，将当前元素加入窗口和；当窗口和超过目标值时，左指针右移，从窗口和中减去左指针指向的元素，缩小窗口。
2. 提前返回：一旦窗口和等于目标值，立即返回当前窗口的1-based索引，保证返回的是最先出现的子数组。
3. 边界处理：遍历完整个数组仍未找到符合条件的子数组时，返回[-1]。

验证示例 #

• 示例1：遍历到右指针索引3（元素7）时，窗口和为13>12，左指针右移至1，窗口和变为12，返回[2,4]，符合预期。
• 示例2：遍历到右指针索引4（元素5）时，窗口和恰好为15，直接返回[1,5]，符合预期。

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