确定数组是否包含两个等于某个总和的元素？

Question

// Checks whether the array contains two elements whose sum is s.
// Input: A list of numbers and an integer s
// Output: return True if the answer is yes, else return False

public static boolean calvalue (int[] numbers, int s){
for (int i=0; i< numbers.length; i++){
    for (int j=i+1; j<numbers.length;j++){
        if (numbers[i] < s){
            if (numbers[i]+numbers[j] == s){
                return true;
                }
            }
        }
    }
    return false;
}

Answer 1

这可以在O(n)中实现.

1. 从列表中创建一个哈希支持的集合,使其包含列表的所有元素.这需要O(n).
2. 遍历n列表中的每个元素,计算s-n = d并检查d集合中是否存在.如果d存在,那么n+d = s,返回true.如果您在没有找到合适的情况下通过列表d,则返回false.这是通过列表的单次传递实现的,每次查找都采用O(1),因此该步骤也需要O(n).

Answer 2

这篇文章的其他答案中提到的解决方案以及其他一些答案(例如使用位图而不是哈希表)出现在以下重复项和问题的略微变化中:
• 在数组中查找两个元素总和为k,
• 从一个数组中找到一对元素,其总和等于给定数字,
• 确定集合中是否存在两个元素,其总和正好相同,
• 检查2个数组是否加起来,
• 在数组中查找添加到给定总和的数字对,
• 设计算法以查找数组中总和为a的所有整数对,
• 给定未排序的数组,找到数组中任何两个元素,其总和等于t,
• 一种递归算法,用于在一个数组中找到两个整数,它们总和为给定的整数,
• 在未排序的数组中找到等于给定总和的2个数字,
• 找到两个元素,使得sum等于给定值,
•和,每个谷歌,许多更多.

Answer 3

你可以通过对数组进行排序来解决这个问题,然后保持2个指向数组开始和结束的指针,并通过移动两个指针找到2个数字.排序步骤采用O(nlog n),第二步采用O(n).

正如@Adam指出的那样,从数组中删除重复元素也是很好的,这样如果数组包含许多重复数字,您可以减少第二步的时间.

至于如何做第二步:

• 如果当前2个数字的总和大于n,则向后移动指针.
• 如果当前2个数字的总和小于n,则将指针向前移动.
• 当两个指针指向同一个元素时停止并拒绝.如果sum等于n,则接受.

为什么这是正确的(我使用右端表示较大的末端,左端表示较小的末端):

• 如果sum大于n,则使用右端没有意义,因为大于当前左端的所有数字都会使其变差.
• 如果sum小于n,则使用左端没有意义,因为所有小于当前右端的数字都会使其变差.
• 在每一步中,我们将在删除的数字和剩余的数字之间经历所有可能的组合(逻辑上).最后,我们将耗尽所有数字对之间可能的所有组合.