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() < 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.
- return
false
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<Long> set = new HashSet<>(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.