Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:
nums[a] + nums[b] + nums[c] == nums[d], anda < b < c < d
Example 1:
Input: nums = [1,2,3,6] Output: 1 Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.
Example 2:
Input: nums = [3,3,6,4,5] Output: 0 Explanation: There are no such quadruplets in [3,3,6,4,5].
Example 3:
Input: nums = [1,1,1,3,5] Output: 4 Explanation: The 4 quadruplets that satisfy the requirement are: - (0, 1, 2, 3): 1 + 1 + 1 == 3 - (0, 1, 3, 4): 1 + 1 + 3 == 5 - (0, 2, 3, 4): 1 + 1 + 3 == 5 - (1, 2, 3, 4): 1 + 1 + 3 == 5
Constraints:
4 <= nums.length <= 501 <= nums[i] <= 100
Solution 1: Brute force (224ms)
Enumerate a, b, c, d.
Time complexity: O(C(n, 4)) = O(n4/24)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int countQuadruplets(vector<int>& nums) { const int n = nums.size(); int ans = 0; for (int a = 0; a < n; ++a) for (int b = a + 1; b < n; ++b) for (int c = b + 1; c < n; ++c) for (int d = c + 1; d < n; ++d) ans += nums[a] + nums[b] + nums[c] == nums[d]; return ans; } }; |
Solution 2: Static frequency table + binary search (39ms)
For each element, we store its indices (sorted).
Given a, b, c, target t = nums[a] + nums[b] + nums[c], we check the hashtable and use binary search to find how many times it occurred after index c.
Time complexity: O(n3/6*logn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int countQuadruplets(vector<int>& nums) { constexpr int kMax = 100; const int n = nums.size(); int ans = 0; vector<vector<int>> m(kMax + 1); for (int i = 0; i < n; ++i) m[nums[i]].push_back(i); for (int a = 0; a < n; ++a) for (int b = a + 1; b < n; ++b) for (int c = b + 1; c < n; ++c) { const int t = nums[a] + nums[b] + nums[c]; if (t > kMax) continue; ans += end(m[t]) - lower_bound(begin(m[t]), end(m[t]), c + 1); } return ans; } }; |
Solution 3: Dynamic frequency table (29ms)
Similar to 花花酱 LeetCode 1. Two Sum, we dynamically add elements (from right to left) into the hashtable.
Time complexity: O(n3/6)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int countQuadruplets(vector<int>& nums) { constexpr int kMax = 100; const int n = nums.size(); int ans = 0; vector<int> m(kMax + 1); // for every c we had seen, we can use it as target (nums[d]). for (int c = n - 1; c >= 0; ++m[nums[c--]]) for (int a = 0; a < c; ++a) for (int b = a + 1; b < c; ++b) { const int t = nums[a] + nums[b] + nums[c]; if (t > kMax) continue; ans += m[t]; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment