HackMD
On Two Sum II - Leetcode 167
Why using the two pointers approach we can't skip a pair which sums to a target.
We will use induction for proof.
Assume our indexes are i (left) and j (right) and we haven't found the solution yet.
If numbers[i] + numbers[j] = target then the solution is found.
If numbers[i] + numbers[j] < target then (because numbers is sorted) all possible sums with the fixed left element (number[i] + numbers[k], k = i+1,...,j) are less than the target. It means there is no point to consider index i any more. That's why we switch i to the next position i+1.
If numbers[i] + numbers[j] > target then all possible sums with the fixed right element (number[k] + numbers[j], k = i,..,j-1) are greater than the target. It means there is no point to consider index j any more and we switch it to j-1.
Repeat the induction step.
Sources
