46. Twin Value Pairs
A warehouse scans parcel weights into the array nums. Two parcels are twins when they sit at different positions i and j with i < j and have exactly the same weight.
Return the number of twin pairs. Every pair of positions is counted once, so three parcels of the same weight make three pairs.
Checking every pair of positions is too slow for the largest input. Count how many times each weight occurs, or keep a running tally while scanning, to finish in linear time. The answer fits in a 32-bit signed integer.
Example 1
- Input:
- nums = [3,1,3,3,1]
- Output:
- 4
- Explanation:
The three 3s give 3 pairs and the two 1s give 1 pair, so the answer is 4.
Example 2
- Input:
- nums = [5,6,7]
- Output:
- 0
- Explanation:
All weights differ, so there are no twin pairs.
Constraints
1 ≤ nums.length ≤ 104
-109 ≤ nums[i] ≤ 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(n)