Approach

For each possible (q, r) with r - q > 1:
1. For all p < q-1, count the frequency of nums[p] * nums[r] and store in a hash map left.
2. For all s > r+1, count the frequency of nums[q] * nums[s] and store in a hash map right.
3. For each product in left, if it exists in right, add left[prod] * right[prod] to the answer.
Return the total answer.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int countSpecialQuadruplets(vector<int>& nums) {\n        int n = nums.size(), ans = 0;\n        for (int q = 1; q < n-4+2; ++q) {\n            for (int r = q+2; r < n-1; ++r) {\n                unordered_map<int, int> left, right;\n                for (int p = 0; p < q-1; ++p) left[nums[p]*nums[r]]++;\n                for (int s = r+2; s < n; ++s) right[nums[q]*nums[s]]++;\n                for (auto& [prod, cnt] : left) {\n                    if (right.count(prod)) ans += cnt * right[prod];\n                }\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> countSpecialQuadruplets</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> nums.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">size</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(), ans </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        for</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> q </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">; q </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">-</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">4</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">+</span>&#

Related Tags