Understanding the problem

Almost every array question starts the same way. You need to know something about a value relative to the others (has it appeared before, how often, at which index), and the first solution is to go and look:

for i in range(n):
    for j in range(n):
        if i != j and a[i] == a[j]:
            return True

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        if (i != j && a[i] == a[j])
            return true;

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (i != j && a[i] == a[j])
            return true;

for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++)
        if (i !== j && a[i] === a[j])
            return true;

for i in 0..n {
    for j in 0..n {
        if i != j && a[i] == a[j] {
            return true;
        }
    }
}

hasDuplicate :: Eq a => [a] -> Bool
hasDuplicate a = or [ a !! i == a !! j | i <- [0 .. n - 1], j <- [0 .. n - 1], i /= j ]
  where n = length a

It is correct. On the eight-element example in the question it returns immediately. Then the array is a hundred thousand elements and the inner scan runs a hundred thousand times for each of them: ten billion comparisons, several minutes, for a question whose answer takes a fraction of a second.

The waste is specific and worth naming. You are re-deriving the same fact, which values are present, once per element, and throwing it away each time.

A hash map turns "is this value present?" from a walk over the array into an arithmetic operation. The key is run through a hash function to get a bucket number, and the answer is wherever that bucket points. The array's length stops mattering.

So the inner loop disappears:

seen = set()
for x in a:
    if x in seen:
        return True
    seen.add(x)

std::unordered_set<int> seen;
for (int x : a) {
    if (seen.count(x)) return true;
    seen.insert(x);
}

Set<Integer> seen = new HashSet<>();
for (int x : a) {
    if (seen.contains(x)) return true;
    seen.add(x);
}

const seen = new Set();
for (const x of a) {
    if (seen.has(x)) return true;
    seen.add(x);
}

let mut seen = HashSet::new();
for &x in a {
    if !seen.insert(x) {          // insert returns false if x was already there
        return true;
    }
}

hasDuplicate :: Ord a => [a] -> Bool
hasDuplicate = go Set.empty
  where
    go _ [] = False
    go seen (x : xs)
      | Set.member x seen = True
      | otherwise = go (Set.insert x seen) xs

One pass, one O(1) question per element, O(n) overall. The saving is not a constant factor; it is a change of shape, from n² to n.

Say "expected O(1)", not "O(1)", if you are asked precisely. Hashing is constant on average. Adversarial keys can collide into one bucket and degrade a lookup to O(n), which is why hash functions in real languages are randomised per process.

Once you know the tool, the problem is no longer "use a hash map". It is choosing the key so that the thing you want becomes a lookup. Three problems, three keys:

• Duplicate detection: key on the value itself. Present or not.
• Two numbers summing to a target: key on the value, look up target − x. You are asking whether the partner has already gone past.
• Subarrays summing to k: key on the running total, not on any element. Two equal prefix sums mean the stretch between them sums to zero, and the general version of that gives the whole answer in one pass.

That last one is the jump worth practising. Nothing in the question mentions prefix sums; you have to notice that the quantity worth remembering is not any value in the array but a fact about everything seen so far.

One ordering bug accounts for most wrong answers in this pattern. Inside the loop you both query the map and update it, and the order matters:

for i, x in enumerate(a):
    if target - x in seen:      # query first
        return (seen[target - x], i)
    seen[x] = i                 # then insert

std::unordered_map<int, int> seen;                 // value -> index
for (int i = 0; i < (int)a.size(); ++i) {
    auto it = seen.find(target - a[i]);            // query first
    if (it != seen.end()) return {it->second, i};
    seen[a[i]] = i;                                // then insert
}

Map<Integer, Integer> seen = new HashMap<>();      // value -> index
for (int i = 0; i < a.length; i++) {
    Integer j = seen.get(target - a[i]);           // query first
    if (j != null) return new int[] {j, i};
    seen.put(a[i], i);                             // then insert
}

const seen = new Map();                           // value -> index
for (let i = 0; i < a.length; i++) {
    if (seen.has(target - a[i])) return [seen.get(target - a[i]), i];   // query first
    seen.set(a[i], i);                                                 // then insert
}

let mut seen = HashMap::new();                     // value -> index
for (i, &x) in a.iter().enumerate() {
    if let Some(&j) = seen.get(&(target - x)) {    // query first
        return Some((j, i));
    }
    seen.insert(x, i);                             // then insert
}

pairSum :: Int -> [Int] -> Maybe (Int, Int)
pairSum target = go Map.empty . zip [0 ..]
  where
    go _ [] = Nothing
    go seen ((i, x) : rest) = case Map.lookup (target - x) seen of
      Just j  -> Just (j, i)                       -- query first
      Nothing -> go (Map.insert x i seen) rest     -- then insert

Insert first and an element can match itself. On a = [3, 5] with target 6, inserting 3 before querying finds 6 − 3 = 3 already present and reports the pair (0, 0). The array does not contain two 3s; you matched the element with its own reflection.

The same bug appears as an off-by-one in counting problems, where it silently inflates the total instead of returning an impossible index. That version is harder to spot, which is why the habit is worth fixing now: query, then insert, always.

Hashing buys time with memory, and there are two cases where the trade is bad.

The input is already sorted. Sortedness is information you have already paid for. Two pointers exploit it in O(1) extra space, where a hash map spends O(n) to ignore it. If a question goes out of its way to tell you the array is sorted, that is the interviewer telling you which pattern they want.

The data does not fit. A map over a hundred million distinct keys is gigabytes. At that size an external sort followed by a linear scan wins, despite being asymptotically worse, because it streams. Knowing that O(n log n) can beat O(n) in practice is the kind of answer that separates candidates.

Every problem in this section is built on the same reflex (notice the repeated lookup, pick the key that collapses it), and they are ordered so the key gets less obvious as you go: the value itself, then a count, then a running total, then a running product, and finally no hash map at all, because the array has to become one. Do them in order.