Count pairs summing to target

Problem Count the pairs (i < j) with nums[i] + nums[j] == target — duplicates in the array count multiple times.

Input / Output

• Input: int array nums, int target. Output: pair count.

Constraints

• n up to 10^5; O(n) expected.

Example

• nums = [1,1,2,3], target = 4 → 2 ((1,3) twice); nums = [2,2,2], target = 4 → 3 (C(3,2)).

Expected approach

• One-pass frequency map: for each x, add freq[target − x] to the count BEFORE inserting x (counts only earlier partners → each pair once, self-pairs handled naturally). O(n)/O(n). Two-pass alternative with full counts needs the x == target/2 correction (C(f,2)) and halving — messier; the one-pass order trick avoids it. Sorted two-pointer version must multiply run lengths on duplicate blocks — a good probe. Contrast with "return all pairs" and "unique values only" variants.