确定一个列表包含两个具有给定和的元素

Question

面试时，我被要求用以下合同写一份方法：

boolean checkList(List<Long> list, long sum){...}

例如，对于参数，它必须返回true：

({1,2,3,4,5,6}，9)因为4+5 =9

它必须返回假的论点：

({0,10,30}，11)因为没有和11的两个元素的组合

我建议这样的代码：

boolean checkList(List<Long> list, long expectedSum) {
    if (list.size() < 2) {
        return false;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        for (int k = i; k < list.size(); k++) {
            if ((list.get(i) + list.get(k)) == expectedSum) {
                return true;
            }
        }
    }
    return false;
}

但面试官要求我改进解决方案。多么?

Answer 1

解决这个难题有很多种方法。你的方法似乎很好。它很简单，也很容易理解。但是，可以用列表的方法替换内环：

public static boolean checkList_contains(List<Integer> list, int sum) {
    if (list.size() < 2) {
        return false;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.contains(sum - list.get(i)))
            return true;
    }
    return false;
}

它试图通过调用contains来查找缺少的值。

然后，您可以使用现代流而不是用于循环：

public static boolean checkList_streams(List<Integer> list, int sum) {
    return list.stream()
            .map(x -> sum - x)
            .filter(list::contains)
            .findAny()
            .isPresent();
}

但是在这里，应该允许它使用相同的元素两次。

这两种解决方案都非常低效。两者都有O(n平方米)的运行时间。

如果您期望得到一个排序列表，您可以使用从左和右移动的两个索引，直到找到匹配的对(这就是@200_success所写的)：

public static boolean checkList_sorted_list(List<Integer> list, int sum) {
    int lowerIndex = 0;
    int upperIndex = list.size() - 1;
    while (lowerIndex < upperIndex) {
        int testSum = list.get(lowerIndex) + list.get(upperIndex);
        if (testSum > sum) upperIndex --;
        else if (testSum < sum) lowerIndex ++;
        else return true;
    }
    return false;
}

这是在O(n)。