188. Zero-Sum Pair Window
A stockroom scale reports the weight of every item in the array nums, already sorted from lightest to heaviest. A shipping crate holds exactly two items, and a crate is acceptable when the total weight of its two items does not exceed target. Weights can be negative because some items are helium balloons that pull upward.
Count the pairs of positions (i, j) with i < j whose two weights add up to target or less. Pairs are identified by position, so two equal weights at different positions form separate pairs.
Example 1
- Input:
- nums = [-4,-1,0,3,6], target = 2
- Output:
- 6
- Explanation:
The pairs with a total of at most 2 are (-4,-1), (-4,0), (-4,3), (-4,6), (-1,0) and (-1,3), so 6 pairs qualify; (0,3) = 3 and everything heavier exceeds 2.
Example 2
- Input:
- nums = [2,2,2], target = 4
- Output:
- 3
- Explanation:
Each of the three pairs of equal weights adds up to exactly 4, which is allowed.
Example 3
- Input:
- nums = [5,6,7], target = 3
- Output:
- 0
- Explanation:
Even the lightest pair adds up to 11, so no pair qualifies.
Constraints
1 ≤ nums.length ≤ 104
-109 ≤ nums[i] ≤ 109
nums is sorted in non-decreasing order
-2 * 109 ≤ target ≤ 2 * 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)