Problem
You are given an array nums
consisting of positive integers.
A special subsequence is defined as a subsequence of length 4, represented by indices (p, q, r, s)
, where p < q < r < s
. This subsequence must satisfy the following conditions:
nums[p] * nums[r] == nums[q] * nums[s]
- There must be at least one element between each pair of indices. In other words,
q - p > 1
,r - q > 1
ands - r > 1
.
Return the number of different special subsequences in nums
.
Example 1
|
|
Example 2
|
|
Constraints
7 <= nums.length <= 1000
1 <= nums[i] <= 1000
Examples
Solution
Method 1 – Hash Map Pair Product Counting
Intuition
We want to count quadruples (p, q, r, s) with p < q < r < s, q - p > 1, r - q > 1, s - r > 1, and nums[p] * nums[r] == nums[q] * nums[s]. For each possible (q, r) pair, we can count the number of valid p < q-1 and s > r+1 such that nums[p] * nums[r] == nums[q] * nums[s] by precomputing products to the left and right using hash maps.
Approach
- For each possible (q, r) with r - q > 1:
- For all p < q-1, count the frequency of nums[p] * nums[r] and store in a hash map left.
- For all s > r+1, count the frequency of nums[q] * nums[s] and store in a hash map right.
- For each product in left, if it exists in right, add left[prod] * right[prod] to the answer.
- Return the total answer.
Code
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^3)
, since for each (q, r) pair, we scan up to n for p and s. - 🧺 Space complexity:
O(n)
, for the hash maps per (q, r) pair.