Two Pointers
The two pointers technique: pairs with a given sum and a sliding window in O(n).
The idea: two indices walk along the array only forward (or towards each other) and never go back. Each pointer moves at most n times — O(n) total instead of the O(n²) of checking all pairs.
Classic number one: in a SORTED array, find a pair with sum X. Put the pointers at the ends: if the sum is too small — move the left one right (the sum grows), if too large — the right one left.
A pair with sum X. Enter: 5 12, then the sorted array 1 3 5 7 9
Why this is correct: if a[l] + a[r] < X, then a[l] paired with ANY element left of r gives even less — so a[l] can be safely discarded. Symmetrically for the right end. No possible pair is ever lost.
Classic number two — the sliding window: both pointers move in the same direction. Let's find the longest segment whose sum does not exceed S: the right end expands the window, the left end shrinks it when the sum exceeds the limit.
The longest segment with sum at most S. Enter: 6 8, then 2 4 1 3 5 2
Note: the inner while does not make the algorithm quadratic — over the whole run the left pointer moves at most n times in total.
The palindrome check you wrote in the language course is also two pointers moving towards each other. Solve the attached problem "Palindrome Check", now understanding it as a special case of the technique, and mark the lesson as completed.