1222. Twin Distance Total
A warehouse scanner logs one item code per shelf slot, in order along an aisle. Two slots are twins when they hold the same code. The distance between twin slots i and j is j - i.
Given the array nums of codes, return the sum of the distances over every pair of indices i < j with nums[i] == nums[j]. Return 0 when no code repeats. The total can exceed 32 bits, so return it as a 64-bit integer.
Aim for O(n) time and O(n) extra space: remember, for each code, how many slots and what index sum you have seen so far.
Example 1
- Input:
- nums = [31,8,31,-4,8,31,77,-4,31]
- Output:
- 34
- Explanation:
Code 31 sits at indices 0, 2, 5 and 8 (distances 2+5+8+3+6+3 = 27), code 8 at 1 and 4 adds 3, and code -4 at 3 and 7 adds 4, for 34.
Example 2
- Input:
- nums = [-20,-20,53,9,14]
- Output:
- 1
- Explanation:
Only -20 repeats, at indices 0 and 1, so the total is a single distance of 1.
Example 3
- Input:
- nums = [900,-45,12,-45,0,7]
- Output:
- 2
- Explanation:
Only -45 repeats, at indices 1 and 3, so the total is 2.
Constraints
1 ≤ n ≤ 1000
-109 ≤ nums[i] ≤ 109
The answer fits in a 64-bit integer.
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)