Two pointers

When should I use two pointers?

When a candidate answer is a pair of positions, and you can look at one pair and rule out every other pair that shares one of its ends. On a sorted array a sum that is too small rules out the whole row of pairs starting at the left index, and a sum that is too big rules out the whole column ending at the right index. The same shape appears in a different form when a read pointer and a write pointer run in the same direction, and again when a slow and a fast runner chase each other down a linked list.

Why does the two-pointer scan not miss a pair?

Because a pointer only moves when every pair it is about to abandon has already been proved impossible. With the array sorted, nums[l] is the smallest value still in play, so if nums[l] + nums[r] is below the target then nums[l] paired with anything left is also below it. Moving l past that position discards a row of the candidate grid, and nothing in that row could ever have been the answer. Say that argument out loud in the room; it is what an interviewer means by “why is that correct?”.

What is the difference between two pointers and a sliding window?

A sliding window is two pointers moving in the same direction, bounding a contiguous stretch whose contents you summarize as you go. The converging form starts at both ends and moves them toward each other, and what it bounds is a set of candidate pairs rather than a stretch you care about. Both keep an invariant about what has already been ruled out, which is why the window is the natural next pattern to learn.

Does two pointers always need a sorted array?

The converging form does, because the discarding argument is built on order: it needs nums[l] to be the smallest value left and nums[r] the largest. Run it on an unsorted array and it will still terminate and still look plausible, and it will quietly walk past pairs that work. The same-direction form does not need order, because it is filtering or compacting rather than searching pairs, and the runner form on a linked list does not either.

If I sort the array first, do I lose the original indices?

Yes, and that decides which tool to reach for. Two Sum II hands you a sorted array and wants positions in that array, so two pointers fits. Plain Two Sum wants positions in the original order, so sorting would destroy the answer and a hash map is the right call: one pass, O(n) time, O(n) space. If you must sort and still need the original positions, sort pairs of (value, index) instead and pay the extra space.