Как определить, есть ли в списке 2 элемента с указанной суммой?

Question

На собеседовании меня попросили написать метод со следующим контрактом:

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

, например, он должен вернуть true для аргументов:
({1,2,3,4,5,6}, 9) потому что 4 + 5 = 9

и он должен возвращать false для аргументов:

({0,10,30}, 11), потому что нет комбинации 2 элементовс суммой 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(List<Long> list, long expectedSum) {
    if(list.size() < 2) {
        return false;
    }
    HashSet<Long> hs = new HashSet<Long>();
    for(long i : list) {
        hs.add(i);
    }

    for(int i=0; i< list.size(); i++) {
        if(hs.contains(expectedSum - list.get(i))) {
            return true;
        }
    }
    return false;
}

Answer 2

Также сделайте хэширование.Есть и другие решения этой проблемы, расположенные здесь .

// Java implementation using Hashing 
import java.io.*; 
import java.util.HashSet; 

class PairSum 
{ 
    static void printpairs(int arr[],int sum) 
    {        
        HashSet<Integer> s = new HashSet<Integer>(); 
        for (int i=0; i<arr.length; ++i) 
        { 
            int temp = sum-arr[i]; 

            // checking for condition 
            if (temp>=0 && s.contains(temp)) 
            { 
                System.out.println("Pair with given sum " + 
                                    sum + " is (" + arr[i] + 
                                    ", "+temp+")"); 
            } 
            s.add(arr[i]); 
        } 
    } 

    // Main to test the above function 
    public static void main (String[] args) 
    { 
        int A[] = {1, 4, 45, 6, 10, 8}; 
        int n = 16; 
        printpairs(A,  n); 
    } 
} 

Answer 3

Один лайнер с использованием Java-8:

public boolean checkList(List<Long> list, long expectedSum) {
    Set<Long> hashSet = new HashSet<>(list);
    return IntStream.range(0, list.size())
                    .anyMatch(i -> hashSet.contains(expectedSum - list.get(i)));
}

Answer 4

возможно, посмотрите на каждое число и посмотрите, есть ли общее число минус это число в списке, поэтому

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