为何基于AbstractList的LeetCode 3Sum解法性能更优？

问题背景 #

在解决3Sum问题时，我发现基于AbstractList的解法性能远优于直接实现核心逻辑的版本：

基于AbstractList的代码（性能更优） #

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    private List<List<Integer>> res;
    public List<List<Integer>> threeSum(int[] nums) {
        int target = 0;
        return new AbstractList<List<Integer>>() {
            public List<Integer> get(int index) {
                init();
                return res.get(index);
            }
            public int size() {
                init();
                return res.size();
            }
            private void init() {
                if (res != null) return;
                Arrays.sort(nums);
                int l, r;
                int sum;
                Set<List<Integer>> tempRes = new HashSet<>();
                for (int i = 0; i < nums.length - 2; ++i) {
                    l = i + 1;
                    r = nums.length - 1;
                    while (l < r) {
                        sum = nums[i] + nums[l] + nums[r];
                        if (sum == target) {
                            List<Integer> t = new ArrayList<>();
                            t.add(nums[i]);
                            t.add(nums[l]);
                            t.add(nums[r]);
                            tempRes.add(t);
                        }
                        if (sum < target) ++l;
                        else --r;
                    }
                }
                res = new ArrayList<List<Integer>>(tempRes);
            }
        };
    }
}

直接实现核心逻辑的代码（耗时约300ms） #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int target = 0;
        Arrays.sort(nums);
        int l, r;
        int sum;
        Set<List<Integer>> tempRes = new HashSet<>();
        for (int i = 0; i < nums.length - 2; ++i) {
            l = i + 1;
            r = nums.length - 1;
            while (l < r) {
                sum = nums[i] + nums[l] + nums[r];
                if (sum == target) {
                    List<Integer> t = new ArrayList<>();
                    t.add(nums[i]);
                    t.add(nums[l]);
                    t.add(nums[r]);
                    tempRes.add(t);
                }
                if (sum < target) ++l;
                else --r;
            }
        }
        return new ArrayList<List<Integer>>(tempRes);
    }
}

问题：为何基于AbstractList的版本性能更优？我猜测是否是因为评测器读取列表内容时才触发计算？

原因分析 #

你的猜测完全正确，核心原因是延迟初始化（懒加载）结合评测系统的计时机制：

• 执行时机的差异
  直接实现的版本在threeSum方法被调用后，会立刻执行所有计算逻辑——包括数组排序、双指针遍历、结果去重、HashSet转ArrayList，所有操作都在方法返回前完成，这部分耗时会被全部统计到threeSum方法的执行时间里。
  而AbstractList版本的threeSum方法仅仅创建并返回一个自定义的AbstractList子类实例就结束了，真正的计算逻辑被封装在init()方法中，只有当评测器后续调用返回列表的size()或get()方法（比如验证答案时需要统计结果数量、遍历结果元素）时，init()才会被触发执行。

• 评测系统的计时规则
  评测系统主要统计的是目标方法（即threeSum）本身的执行耗时，而不是整个测试流程（包括后续验证答案的步骤）的总耗时。AbstractList版本把计算逻辑延迟到方法返回后执行，这部分耗时不会被计入threeSum方法的统计时间，因此提交结果中显示的耗时会显著低于直接实现的版本。

• 额外的优化保障
  AbstractList版本的init()方法带有判重逻辑（if (res != null) return;），确保计算逻辑只会被执行一次，不会因为多次调用size()或get()而重复计算，避免了不必要的性能损耗。

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