本文揭示 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<list>></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 → <code>left++（需增大总和）；-
sum > 0→right--（需减小总和）； -
sum == 0→ 记录结果，并主动跳过左右侧重复值，避免重复三元组；
-
关键剪枝：若
nums[i] > 0，因数组已升序，后续所有组合和必 > 0，可直接break。
以下是 Python 版清晰实现（含完整去重与边界处理）：
def threeSum(nums):
if len(nums) < 3:
return []
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
# 剪枝：首个数大于0，后续无解
if nums[i] > 0:
break
# 去重：跳过与前一元素相同的首数
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
# 去重：跳过重复的 left 和 right
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res? 注意事项：
- Java 版需使用
ArrayList替代HashSet存储结果（因HashSet<list></list>依赖List的hashCode()，而ArrayList默认实现基于元素顺序，相同内容列表哈希值一致，但仍推荐双指针内去重，避免哈希开销与不确定性）；- 不要依赖
AbstractList技巧应对面试或生产——面试官考察的是你的算法思维、边界处理与代码鲁棒性，而非评测系统的盲区；- 该思路可自然延伸至「四数之和」（固定两个数 + 双指针）或「最接近三数之和」（记录最小绝对差）等变种问题。
掌握排序与双指针的本质逻辑，远比钻评测空子更有价值——它构建的是你解决数组类问题的底层肌肉记忆，而非一次性的“低分通过”。
