java - 这个解决方案可以优化吗？

Question

给定一个数组 L= [3,4,6,7,2,1] 和一个整数 Z = 8，找到属于 L 的 2 个整数 X,Y，使得 X + Y = Z

这是一种可能的解决方案 -

public static void findIntegersSum(List<Integer> list, int z) {

    for(int i = 0 ;i < list.size(); i++) {
        for(int j = i+1 ; j< list.size(); j++) {
            if(list.get(i) + list.get(j) == z) {
                System.out.println(" X = " + list.get(i) + "\t Y=" + list.get(j));
                return;
            }
        }
    }
    System.out.println(" No match found !!");
}

问题是 - 我们可以优化上述解决方案吗？

Answer 1

您可以使用 Set 的实现来完成此操作数据类型。 Set 通常被实现为 Hash table (Java 中的 HashSet)或 Binary Search Tree (Java 中的 TreeSet)。哈希表实现通常使用更多内存，但在平均情况下具有恒定时间 O(1) 查找和插入，树实现使用线性内存，但在平均情况下具有 O(log n) 查找和插入。

使用该数据结构的伪代码如下:

S = set(L) // Iterate through L and put it in a set, O(n) or O(n log n)
for element in L: // O(n)
    if S.has(Z - element): // O(1) or O(log n) depending on HashSet or TreeSet
        X = element
        Y = Z - element
        break

此解决方案的复杂度为 O(n) 或 O(n log n)，而不是 O(n^2)。