At a party, everyone writes their name on a board as they arrive; to find your dance partner you just check the board instead of asking every guest.
Clues that point here
→ Find a pair with a sum or difference in an unsorted array
→ "Have I seen this before?"
→ Return indexes, so sorting isn't allowed
→ Need O(n) time
Not this pattern when
✕ The array is sorted and O(1) space is required (two pointers)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Hash Map Lookup (Complement) · template
Map<Integer, Integer> indexOf = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (indexOf.containsKey(need)) return new int[]{indexOf.get(need), i};
indexOf.put(nums[i], i); // store after checking (no self-pairs)
}
return new int[0];