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

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)。