The starter contains a working hasPairSum(nums, target): it returns true when two different positions in nums hold values adding up to target. It is correct and it is O(n^2). Rewrite it so it runs in O(n), keeping the exact same behaviour.
- The two values must come from two different indices, but they may be equal values —
[3, 3] with target 6 is true - A single element can never pair with itself:
[4] with target 8 is false - Negative numbers and zero are allowed
- One test runs 150,000 elements with no answer present. The quadratic version needs billions of comparisons there and will not finish — the linear one takes milliseconds