LeetCode Two Sum III超时问题：如何优化现有实现？

嘿，我看了你这个TwoSum III的实现，超时问题其实出在add方法的效率上，咱们来拆解下问题，再给出优化方案：

原实现的问题分析 #

你原来的思路是把所有可能的两数之和提前存在res集合里，每次add新数字时，遍历已有的所有数字计算和并存起来。这个思路的问题在于：

• add操作的时间复杂度是O(n)（n是当前已存数字的数量），如果频繁调用add添加大量元素，总时间复杂度会变成O(n²)，数据量一大就很容易超时。
• 另外，res集合会随着数字增多变得无比庞大，占用的内存也会直线飙升，这也是个隐形的性能问题。

优化方案：用哈希表记录数字出现次数 #

咱们换个思路，不提前计算所有和，而是在find的时候再去查找是否存在符合条件的数字对。具体来说：

• 用一个HashMap<Integer, Integer>来存储每个数字出现的次数，key是数字本身，value是这个数字出现的次数。
• add操作：直接把数字存入哈希表，次数加1，时间复杂度O(1)。
• find操作：遍历哈希表中的每个数字num，计算需要匹配的目标数字target = value - num，然后分两种情况判断：
  1. 如果num != target：只要哈希表中存在target，就返回true。
  2. 如果num == target：需要这个数字的出现次数至少是2次（因为要两个相同的数字相加得到value）。

优化后的代码实现 #

class TwoSum {
    private Map<Integer, Integer> countMap;

    /** Initialize your data structure here. */
    public TwoSum() {
        countMap = new HashMap<>();
    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        countMap.put(number, countMap.getOrDefault(number, 0) + 1);
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            int num = entry.getKey();
            int target = value - num;
            if (countMap.containsKey(target)) {
                // 处理两个相同数字的情况
                if (num != target) {
                    return true;
                } else {
                    // 同一个数字需要至少出现两次
                    if (entry.getValue() >= 2) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

性能对比 #

• add操作从原来的O(n)降到了O(1)，频繁添加元素时效率提升非常明显。
• find操作的时间复杂度是O(n)，但这个n是哈希表中不同数字的数量（如果有很多重复数字，实际n会比原实现的nums大小小很多），整体性能会比原实现好很多，不会轻易超时。

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