我怎样才能降低这个函数的时间复杂度？

Question

问题：

给定一个数字列表和一个数字 k，return 列表中的任意两个数字是否相加为 k。例如，给定 [10, 15, 3, 7] 和 17 的 k，return 为真，因为 10 + 7 为 17。

我相信我提出的解决方案的运行时间复杂度为 O(N^2)，我目前正在致力于创建更高效的代码，并通过浏览代码来确定时间复杂度。非常感谢任何反馈和建议。

import java.util.ArrayList;
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){

        for (int i = 0; i < l.size()-1; i++) {
            for (int j = l.size()-1; j > i; j--) {
                if (l.get(i)+l.get(j)==k) {
                    return true;
                }
            }
        }
        return false;
    }
}

Answer 1

您可以使用 Arrays.sort 对列表进行排序，即 O(n log(n)) 并在 O( n)，使方法 O(n log(n)) 总体：

public class Practice {
    public static boolean isKsumPossible(int[] l, int k) {
        // O(n log(n))
        // Higher numbers to the right, lower numbers to the left
        Arrays.sort(l);
        
        // O(n)
        for (int i0 = 0, i1 = l.length - 1; i0 == i1;) {
            if (l[i0] + l[i1] < k) {
                // If the sum is lesser than the target, increment 
                // the current sum by incrementing the start pointer
                ++i0;
            } else if (l[i0] + l[i1] > k) {
                // If the sum is greater than the target, decrement 
                // the current sum by decrementing the end pointer
                --i1;
            } else {
                // If the sum is equal to the target, return true
                return true;
            }
        }
        
        return false;
    }
}

这是用法 - 它拆分了代码逻辑和 I/O 逻辑，使其可测试：

public class Practice {
    public static void main(String[] args) {
        Scanner numberScanner = new Scanner(System.in);

        System.out.println("Enter 4 numbers of your choice:");
        int[] values = new int[4];
        for (int i = 0; i < 4; i++) {
            values[i] = numberScanner.nextInt();
        }

        System.out.println("-------------");
        System.out.println("Enter K value:");
        int k = numberScanner.nextInt();
        numberScanner.close();

        System.out.println(isKsumPossible(values, k));
    }
}

Answer 2

你可以在一次恒定时间内完成，即 O(n):

boolean hasSum(List<Integer> list, int sum) {
    Set<Integer> found = new HashSet<>();
    for (int i : list) {
        if (found.contains(k - i)) {
            return true;
        }
        found.add(i);
    }
    return false;
}

HashSet操作是常量时间，有2n个，所以时间复杂度是O(n)。

我怎样才能降低这个函数的时间复杂度？

How can I lower this function's time complexity?

java

big-o