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.
8/26/2022There are 3 main parts to cover: The main idea How it works Why it’s relevant When looking through materials Grab a pen and piece of paper Write so a 5 year old can understand
8/25/2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up