Welcome to Subscribe On Youtube
3583. Count Special Triplets
Description
You are given an integer array nums
.
A special triplet is defined as a triplet of indices (i, j, k)
such that:
0 <= i < j < k < n
, wheren = nums.length
nums[i] == nums[j] * 2
nums[k] == nums[j] * 2
Return the total number of special triplets in the array.
Since the answer may be large, return it modulo 109 + 7
.
Example 1:
Input: nums = [6,3,6]
Output: 1
Explanation:
The only special triplet is (i, j, k) = (0, 1, 2)
, where:
nums[0] = 6
,nums[1] = 3
,nums[2] = 6
nums[0] = nums[1] * 2 = 3 * 2 = 6
nums[2] = nums[1] * 2 = 3 * 2 = 6
Example 2:
Input: nums = [0,1,0,0]
Output: 1
Explanation:
The only special triplet is (i, j, k) = (0, 2, 3)
, where:
nums[0] = 0
,nums[2] = 0
,nums[3] = 0
nums[0] = nums[2] * 2 = 0 * 2 = 0
nums[3] = nums[2] * 2 = 0 * 2 = 0
Example 3:
Input: nums = [8,4,2,8,4]
Output: 2
Explanation:
There are exactly two special triplets:
(i, j, k) = (0, 1, 3)
nums[0] = 8
,nums[1] = 4
,nums[3] = 8
nums[0] = nums[1] * 2 = 4 * 2 = 8
nums[3] = nums[1] * 2 = 4 * 2 = 8
(i, j, k) = (1, 2, 4)
nums[1] = 4
,nums[2] = 2
,nums[4] = 4
nums[1] = nums[2] * 2 = 2 * 2 = 4
nums[4] = nums[2] * 2 = 2 * 2 = 4
Constraints:
3 <= n == nums.length <= 105
0 <= nums[i] <= 105
Solutions
Solution 1: Enumerate Middle Number + Hash Table
We can enumerate the middle number $\textit{nums}[j]$, and use two hash tables, $\textit{left}$ and $\textit{right}$, to record the occurrence counts of numbers to the left and right of $\textit{nums}[j]$, respectively.
First, we add all numbers to $\textit{right}$. Then, we traverse each number $\textit{nums}[j]$ from left to right. During the traversal:
- Remove $\textit{nums}[j]$ from $\textit{right}$.
- Count the occurrences of the number $\textit{nums}[i] = \textit{nums}[j] * 2$ to the left of $\textit{nums}[j]$, denoted as $\textit{left}[\textit{nums}[j] * 2]$.
- Count the occurrences of the number $\textit{nums}[k] = \textit{nums}[j] * 2$ to the right of $\textit{nums}[j]$, denoted as $\textit{right}[\textit{nums}[j] * 2]$.
- Multiply $\textit{left}[\textit{nums}[j] * 2]$ and $\textit{right}[\textit{nums}[j] * 2]$ to get the number of special triplets with $\textit{nums}[j]$ as the middle number, and add the result to the answer.
- Add $\textit{nums}[j]$ to $\textit{left}$.
Finally, return the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$.
-
class Solution { public int specialTriplets(int[] nums) { Map<Integer, Integer> left = new HashMap<>(); Map<Integer, Integer> right = new HashMap<>(); for (int x : nums) { right.merge(x, 1, Integer::sum); } long ans = 0; final int mod = (int) 1e9 + 7; for (int x : nums) { right.merge(x, -1, Integer::sum); ans = (ans + 1L * left.getOrDefault(x * 2, 0) * right.getOrDefault(x * 2, 0) % mod) % mod; left.merge(x, 1, Integer::sum); } return (int) ans; } }
-
class Solution { public: int specialTriplets(vector<int>& nums) { unordered_map<int, int> left, right; for (int x : nums) { right[x]++; } long long ans = 0; const int mod = 1e9 + 7; for (int x : nums) { right[x]--; ans = (ans + 1LL * left[x * 2] * right[x * 2] % mod) % mod; left[x]++; } return (int) ans; } };
-
class Solution: def specialTriplets(self, nums: List[int]) -> int: left = Counter() right = Counter(nums) ans = 0 mod = 10**9 + 7 for x in nums: right[x] -= 1 ans = (ans + left[x * 2] * right[x * 2] % mod) % mod left[x] += 1 return ans
-
func specialTriplets(nums []int) int { left := make(map[int]int) right := make(map[int]int) for _, x := range nums { right[x]++ } ans := int64(0) mod := int64(1e9 + 7) for _, x := range nums { right[x]-- ans = (ans + int64(left[x*2])*int64(right[x*2])%mod) % mod left[x]++ } return int(ans) }
-
function specialTriplets(nums: number[]): number { const left = new Map<number, number>(); const right = new Map<number, number>(); for (const x of nums) { right.set(x, (right.get(x) || 0) + 1); } let ans = 0; const mod = 1e9 + 7; for (const x of nums) { right.set(x, (right.get(x) || 0) - 1); const lx = left.get(x * 2) || 0; const rx = right.get(x * 2) || 0; ans = (ans + ((lx * rx) % mod)) % mod; left.set(x, (left.get(x) || 0) + 1); } return ans; }