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: the number of index pairs summing to target.

Constraints

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

Example

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