Given a list of integers nums sorted in non-decreasing order (duplicates allowed) and an integer target, return the number of index pairs (i, j) with i < j and nums[i] + nums[j] == target.
Examples
Input: nums = [1, 1, 2, 2, 3, 3], target = 4
Output: 5
Explanation: each of the two 1s pairs with each of the two 3s (4 pairs), plus the pair of 2s.
Input: nums = [2, 2, 2], target = 4
Output: 3
Constraints
0 <= len(nums) <= 10**5- Target: O(n) time, O(1) extra space. A hash map of counts is O(n) space and is not the intended approach.
Goals
- Handle runs of equal values by counting them in blocks
- Treat the case where both pointers sit inside the same run