如何降低两数之和问题Java解法的时间复杂度？

解法优化建议 #

当前代码的问题 #

你现在写的是暴力枚举所有两两组合的解法，两层嵌套循环遍历列表，最坏情况下要执行 n*(n-1)/2 次判断，所以时间复杂度是O(N²)，仅适合数据量很小的场景，数据量过万的时候性能就会明显下降。

优化方案1：哈希集合（时间O(N)，空间O(N)） #

这是该问题最优的时间复杂度解法，思路如下：

• 遍历列表时，记录下已经遍历过的元素
• 对当前元素num，计算目标差值target = k - num，如果target已经在已遍历的集合中，说明存在两个数相加等于k，直接返回true
• 如果不存在，就把当前num加入集合，继续遍历
• 遍历完所有元素都没找到就返回false

对应Java代码：

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

public class Practice {
    public static void main(String[] args) {
        List<Integer> l = new ArrayList<>();
        l.add(10);
        l.add(15);
        l.add(3);
        l.add(7);
        System.out.println(isKsumPossible(l, 17));
    }

    public static boolean isKsumPossible(List<Integer> l, int k){
        Set<Integer> seen = new HashSet<>();
        for (int num : l) {
            int target = k - num;
            if (seen.contains(target)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
}

优化方案2：排序+双指针（时间O(N log N)，空间*O(1)~O(N)*取决于排序实现） #

如果对空间消耗有要求，可以选这个方案，思路如下：

• 先对列表做排序
• 初始化左指针left = 0指向列表最左端，右指针right = l.size() - 1指向列表最右端
• 计算两指针指向元素的和：
  • 和等于k：返回true
  • 和小于k：需要更大的数，左指针右移
  • 和大于k：需要更小的数，右指针左移
• 两指针相遇还没找到就返回false

对应Java代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Practice {
    public static void main(String[] args) {
        List<Integer> l = new ArrayList<>();
        l.add(10);
        l.add(15);
        l.add(3);
        l.add(7);
        System.out.println(isKsumPossible(l, 17));
    }

    public static boolean isKsumPossible(List<Integer> l, int k){
        Collections.sort(l);
        int left = 0;
        int right = l.size() - 1;
        while (left < right) {
            int sum = l.get(left) + l.get(right);
            if (sum == k) {
                return true;
            } else if (sum < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}

快速识别时间复杂度的技巧 #

• 看有几层遍历完整输入规模的嵌套循环：1层就是O(N)，2层就是O(N²)，以此类推
• 代码里用到排序的，默认通用排序的时间复杂度是O(N log N)，如果排序后只有一层单指针/双指针遍历，整体复杂度还是O(N log N)
• 哈希表、数组的随机访问操作都是O(1)，不会拉高整体复杂度
• 递归逻辑可以用主定理推导，常见的二分递归是O(log N)

内容的提问来源于stack exchange，提问作者Anthony Mendez Frias