本文揭示 LeetCode 上一种利用 AbstractList 延迟初始化的“伪加速”技巧本质，并回归算法核心——排序 + 双指针的正确、可复用、工程友好的 O(n²) 解法。
本文揭示 leetcode 上一种利用 `abstractlist` 延迟初始化的“伪加速”技巧本质，并回归算法核心——排序 + 双指针的正确、可复用、工程友好的 o(n²) 解法。
你可能在 LeetCode 提交记录中见过这样一段 Java 代码：它继承 AbstractList，把三数之和的计算逻辑藏在 get() 和 size() 的惰性 init() 调用中，运行耗时显示仅约 20–50ms，远低于常规实现（通常 300ms+）。但请务必注意：这不是算法优化，而是评测机制的“时间测量漏洞”利用。
? 真相：延迟初始化 ≠ 真实加速
LeetCode 的判题系统在计时阶段只测量 threeSum() 方法的返回耗时，而非后续对结果列表的遍历或校验。上述 AbstractList 实现巧妙地将全部计算（排序、双指针扫描、去重）推迟到 get(index) 或 size() 首次被调用时才执行——而此时计时早已结束。系统读取答案时触发 init()，真实运算才发生，但该部分时间不计入提交耗时。
这本质上是一种“作弊式优化”：
- ✅ 表面满足接口契约（返回
List）；- >
- ❌ 违背算法题考察初衷（评估完整求解过程的时间复杂度）；
- ⚠️ 在真实工程场景中完全不可用（如多次调用
get(0)会重复计算，无缓存且线程不安全）。
✅ 正确解法：排序 + 双指针（O(n²) 标准实现）
真正值得掌握的是经典、健壮、可扩展的双指针解法。其核心步骤如下：
-
排序预处理：
Arrays.sort(nums)—— 时间复杂度 O(n log n)，为后续剪枝与去重奠定基础； -
外层遍历固定首元素：索引
i从0到n-3，并跳过重复值（nums[i] == nums[i-1]）； -
双指针搜索剩余两数：在
[i+1, n-1]区间设left和right，根据三数和sum = nums[i] + nums[left] + nums[right]动态收缩：sum →left++（需增大总和）；-
sum > 0→right--（需减小总和）； -
sum == 0→ 记录结果，并主动跳过左右侧重复值，避免重复三元组；
-
关键剪枝：若
nums[i] > 0，因数组已升序，后续所有组合和必 > 0，可直接break。
以下是 Python 版清晰实现（含完整去重与边界处理）：
ArrayList
