I came up with this idea within 5 sec — carefully adjust le and ri pointers from both ends towards center.
- if arr[le] + arr[ri] too big, then move le
- else move ri
- repeat until success or le+1==ri
My friend Ashish was asked a related question — unsorted array .. must return original indices of the pair. It’s relatively easy to adjust my algo to meet this requirement.
- before sorting, save the original indices in a multimap or map<val, set<index>>
- after we found a pair, look up to get the indices.