寻找和为指定值的连续子数组索引问题及Java代码优化求助

需求：从给定数组中找到和为指定值的连续子数组，返回其首尾索引（从1开始计数）的ArrayList。现有代码通过了52个测试用例，但处理大型数组时返回-1，不符合预期。

输入示例：

• arr = {1,2,3,7,5}，n = 5，s = 12
• 预期输出：[2, 4]

原代码：

static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
    ArrayList<Integer> result = new ArrayList<>();
    result.add(0, -1);
    for (int i = 0; i < n; i++) {
        int sum = arr[i];
        for (int j = i+1; j < n; j++) {
            sum += arr[j];
            if (sum == s) {
                result.add(1, j+1);
                result.set(0, i+1);
                return result;
            }
        }
    }
    return result;
}

原代码存在的问题 #

1. 遗漏单个元素匹配的场景：如果数组中存在某个元素直接等于目标值s，原代码的内层循环从i+1开始，不会检查初始的sum=arr[i]是否等于s，直接跳过该情况，导致返回-1。
2. 时间复杂度过高：双重循环的时间复杂度为O(n²)，处理大型数组时会严重超时，程序无法在规定时间内完成遍历，最终返回初始的-1。
3. 结果列表操作逻辑冗余：初始添加-1，找到结果时混合使用set和add，代码不够简洁，容易引发索引操作错误。

优化方案：滑动窗口法（适用于数组元素为正数的场景） #

利用滑动窗口可以将时间复杂度降至O(n)，高效处理大型数组。核心思路是通过左右指针维护一个窗口，动态调整窗口大小来匹配目标和。

修复后的代码：

static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
    ArrayList<Integer> result = new ArrayList<>();
    int left = 0;
    int currentSum = 0;

    for (int right = 0; right < n; right++) {
        currentSum += arr[right];

        // 当当前和超过目标值时，移动左指针缩小窗口
        while (currentSum > s && left <= right) {
            currentSum -= arr[left];
            left++;
        }

        // 找到符合条件的连续子数组
        if (currentSum == s) {
            result.add(left + 1);
            result.add(right + 1);
            return result;
        }
    }

    // 未找到匹配的子数组
    result.add(-1);
    return result;
}

代码说明 #

• 初始化左指针left和当前和currentSum，遍历右指针right扩展窗口。
• 每次将右指针元素加入当前和，若当前和超过目标值，则移动左指针缩小窗口，直到当前和小于等于目标值。
• 当当前和等于目标值时，返回左右指针+1（因为题目要求索引从1开始）。
• 遍历结束未找到匹配时，返回包含-1的列表。

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