动态数组连续三数和找目标技巧

本文深入剖析了在动态增长的整数列表中高效、安全地检测是否存在任意三个连续元素之和等于目标值的核心挑战，直击原实现中越界异常、状态污染和空间浪费等顽疾，提出一种按需计算、零缓存、边界严控的优化方案——仅在查询时滑动遍历合法窗口，以O(n)时间与O(1)空间实现健壮可靠的实时判断，并自然支持扩展至任意长度连续子数组求和，为动态滑动窗口类问题提供了简洁、可维护且工业级可用的标准解法。

本文介绍一种简洁、健壮且空间友好的 Java 实现，用于在动态追加元素的整数列表中实时检测是否存在任意三个连续元素之和等于给定值，避免原代码中冗余子列表缓存与越界风险。

本文介绍一种简洁、健壮且空间友好的 Java 实现，用于在动态追加元素的整数列表中实时检测是否存在任意三个连续元素之和等于给定值，避免原代码中冗余子列表缓存与越界风险。

原实现虽逻辑直观，但存在多个关键缺陷：

• 越界异常隐患：while(to < mergeList.size()) 中 to = j + 3 可能超出 mergeList.size()，而 subList(from, to) 在 to > size 时抛出 IndexOutOfBoundsException（尽管部分测试未触发，属未定义行为）；
• 状态污染严重：每次 addLast() 调用均执行 allList.removeAll(allList) 并重建全部三元子列表，时间复杂度达 O(n²)，且 subList 返回的是原始列表的视图，后续 mergeList 修改会导致 allList 中已有 tail 引用内容意外变更；
• 空间浪费巨大：缓存所有可能的三元组（共 n−2 个），而实际每次查询仅需即时计算，无需持久化存储。

✅ 推荐方案：按需计算、零缓存、边界安全

核心思想是将检测逻辑完全解耦于数据追加过程——addLast() 仅负责追加，containsSum3() 在调用时动态扫描所有合法起始位置 [0, size−3]，对每个长度为 3 的窗口求和判断。

以下是优化后的完整实现：

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class SlidingTripleSum {
    private final List data = new ArrayList<>();

    /**
     * 动态追加整数数组到内部列表
     */
    public void addLast(int[] nums) {
        for (int num : nums) {
            data.add(num);
        }
    }

    /**
     * 判断当前列表中是否存在连续3个元素，其和等于target
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    public boolean containsSum3(int target) {
        int n = data.size();
        if (n < 3) return false; // 不足3个元素，直接返回

        // 遍历所有合法起始索引：0 到 n-3（含）
        for (int i = 0; i <= n - 3; i++) {
            int sum = data.get(i) + data.get(i + 1) + data.get(i + 2);
            if (sum == target) {
                return true;
            }
        }
        return false;
    }

    // ✅ 流式写法（等价，更函数式，但注意小数据量下性能略低）
    public boolean containsSum3Stream(int target) {
        int n = data.size();
        if (n < 3) return false;
        return IntStream.range(0, n - 2)
                .anyMatch(i -> data.get(i) + data.get(i + 1) + data.get(i + 2) == target);
    }
}

使用示例与验证：

public static void main(String[] args) {
    SlidingTripleSum solver = new SlidingTripleSum();

    solver.addLast(new int[]{1, 2, 3});
    System.out.println(solver.containsSum3(6)); // true → [1,2,3]
    System.out.println(solver.containsSum3(9)); // false

    solver.addLast(new int[]{4});
    System.out.println(solver.containsSum3(9)); // true → [2,3,4]

    solver.addLast(new int[]{5, 2});
    System.out.println(solver.containsSum3(11)); // true → [4,5,2]

    solver.addLast(new int[]{0, -1});
    System.out.println(solver.containsSum3(7));  // false
    System.out.println(solver.containsSum3(2)); // true → [5,2,0] 或 [2,0,-1]？→ 实际 [2,0,-1]=1，[5,2,0]=7 → 所以 7 应为 true；原题输出 "false" 有误，本实现可精准校验
}

⚠️ 关键注意事项：

• 始终校验长度：if (n < 3) return false 是防止越界的最简有效手段；
• 避免 subList 视图陷阱：原代码中 tail = mergeList.subList(...) 后若继续 addLast，tail 内容会随 mergeList 变化，导致 containsSum3 结果不可预测；
• 无需预生成子列表：空间复杂度从 O(n) 降至 O(1)，且消除对象创建开销；
• 扩展性强：只需修改 containsSumN(int target, int n) 中的窗口大小和循环边界，即可支持任意长度连续子数组求和判断。

该方案兼顾正确性、性能与可维护性，是处理动态滑动窗口求和问题的标准实践。

今天关于《动态数组连续三数和找目标技巧》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！