java - 检查一个数字是否可以从两个整数列表中求和的最快方法？

Question

所以，我有一个整数列表。我需要找出列表中的任意两个数字(非唯一数字)是否可以添加特定数字。到目前为止我所拥有的:

boolean cs = false;
    t:
    for(Integer i1 : primes) {
        for(Integer i2 : primes) {
            if(i1 + i2 == i) {
                cs = true;
                break t;
            }
        }
    }

不幸的是，随着这个列表变得越来越高(因为每次没有两个和，它必须找到并创建一个新的和以保持序列继续)，这个函数的执行时间呈指数增长。有什么方法可以防止这样的问题吗？当这个函数达到数千个时，它或多或少会因为花费的时间而停止。

Answer 1

首先，对列表进行排序。

然后在列表中启动两个光标，两端各一个。在循环中，将光标下的两个值相加。如果小于您想要的总数，请将左(较小)光标向右(“较大”方向)前进一步。如果总和较大，请将右(较小)光标向左前进一步。

如果有一对总和等于您想要的总数，它将找到它。对列表进行排序需要 O(n log n) 时间，运行游标循环需要 O(n) 时间。总的来说，它的时间复杂度为O(n log n)，希望它足够快以满足您的需求。

编辑

实际上，有一个线性时间、线性空间算法可以做到这一点。假设您的目标数字是k。对于列表中的每个整数 i，将 k - i 插入到哈希集中。然后检查 i 是否已在集合中。如果是，那么一定是因为 k - i 已经在列表的前面遇到过。这可能就是@SpiderPig 暗示的算法。