Determine a list contains two elements with a given sum On interview I was asked to write method with following contract:

boolean checkList(List&lt;Long&gt; list, long sum){...}


for example it has to return true for arguments:
 ({1,2,3,4,5,6}, 9)  because 4+5 = 9

and it have to return false for arguments:  

({0,10,30}, 11)  because there are no combination of 2 elements with sum 11

I suggested code like this:

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


But interviewer asked me to improve the solution. How?
As 200_success mentions, your solution is \$O(n^2)\$, due to the double for loop.

You actually have an error in your inner loop.  You start the inner loop with for (int k = i; ..., but it should be for (int k = i + 1; ....  This means you could return true for an even expected sum when half of that value appears once in the list.

If you correct the above error, the test for list.size() &lt; 2 is unnecessary.  The outer loop will run at most once (size=1) and the inner loop will not run at all, therefore the return false; at the end of the function will be executed.



An \$O(n)\$ solution is:


start with an empty set
for each value x in the list:


if set contains expectedSum - x, return true
add x to the set.

returnfalse


It is important to check for containment before adding the value, or ({1,2,3,4}, 8) would return true, despite not containing a pair of 4’s.

Set&lt;Long&gt; set = new HashSet&lt;&gt;(list.size()*2);
for(long x: list) {
    if (set.contains(expectedSum - x)) {
        return true;
    }
    set.add(x);
}
return false;


The list does not need to be sorted.

The capacity of the HashSet is initialized to double the size of the list, to avoid re-sizings, which would slow the algorithm down.

From the comments: "Why double?" The default load factor for a HashSet is 0.75. If the number of elements in the set exceeds load_factor * capacity, the capacity is increased and the contents rehashed for the new size. If the capacity was set to the size of the list, it would still end up expanding the capacity and rehashing after adding the first 75% of the entries in the list. You need an initial capacity at least 33% larger than the final size to avoid the expansion: list.size()*4/3 + 1 might be sufficient, but is perhaps cutting things a little too fine.  Double seemed a reasonable amount.