Welcome to Subscribe On Youtube
1995. Count Special Quadruplets
Description
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
Solutions
Solution 1: Direct Implementation
This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
Solution 2
This implementation uses hash table. It traverses the relevant values and updates its state as each value is processed. A keyed container records values that must be found or updated efficiently. After all required states have been considered, the maintained result is returned.
Solution 3
This implementation uses hash table. It traverses the relevant values and updates its state as each value is processed. A keyed container records values that must be found or updated efficiently. After all required states have been considered, the maintained result is returned.
-
class Solution { public int countQuadruplets(int[] nums) { int ans = 0, n = nums.length; for (int a = 0; a < n - 3; ++a) { for (int b = a + 1; b < n - 2; ++b) { for (int c = b + 1; c < n - 1; ++c) { for (int d = c + 1; d < n; ++d) { if (nums[a] + nums[b] + nums[c] == nums[d]) { ++ans; } } } } } return ans; } } // Solution 2 class Solution { public int countQuadruplets(int[] nums) { int ans = 0, n = nums.length; int[] counter = new int[310]; for (int c = n - 2; c > 1; --c) { ++counter[nums[c + 1]]; for (int a = 0; a < c - 1; ++a) { for (int b = a + 1; b < c; ++b) { ans += counter[nums[a] + nums[b] + nums[c]]; } } } return ans; } } // Solution 3 class Solution { public int countQuadruplets(int[] nums) { int ans = 0, n = nums.length; int[] counter = new int[310]; for (int b = n - 3; b > 0; --b) { int c = b + 1; for (int d = c + 1; d < n; ++d) { if (nums[d] - nums[c] >= 0) { ++counter[nums[d] - nums[c]]; } } for (int a = 0; a < b; ++a) { ans += counter[nums[a] + nums[b]]; } } return ans; } } -
class Solution { public: int countQuadruplets(vector<int>& nums) { int ans = 0, n = nums.size(); for (int a = 0; a < n - 3; ++a) for (int b = a + 1; b < n - 2; ++b) for (int c = b + 1; c < n - 1; ++c) for (int d = c + 1; d < n; ++d) if (nums[a] + nums[b] + nums[c] == nums[d]) ++ans; return ans; } }; // Solution 2 class Solution { public: int countQuadruplets(vector<int>& nums) { int ans = 0, n = nums.size(); vector<int> counter(310); for (int c = n - 2; c > 1; --c) { ++counter[nums[c + 1]]; for (int a = 0; a < c - 1; ++a) { for (int b = a + 1; b < c; ++b) { ans += counter[nums[a] + nums[b] + nums[c]]; } } } return ans; } }; // Solution 3 class Solution { public: int countQuadruplets(vector<int>& nums) { int ans = 0, n = nums.size(); vector<int> counter(310); for (int b = n - 3; b > 0; --b) { int c = b + 1; for (int d = c + 1; d < n; ++d) { if (nums[d] - nums[c] >= 0) { ++counter[nums[d] - nums[c]]; } } for (int a = 0; a < b; ++a) { ans += counter[nums[a] + nums[b]]; } } return ans; } }; -
class Solution: def countQuadruplets(self, nums: List[int]) -> int: ans, n = 0, len(nums) for a in range(n - 3): for b in range(a + 1, n - 2): for c in range(b + 1, n - 1): for d in range(c + 1, n): if nums[a] + nums[b] + nums[c] == nums[d]: ans += 1 return ans # Solution 2 class Solution: def countQuadruplets(self, nums: List[int]) -> int: ans, n = 0, len(nums) counter = Counter() for c in range(n - 2, 1, -1): counter[nums[c + 1]] += 1 for a in range(c - 1): for b in range(a + 1, c): ans += counter[nums[a] + nums[b] + nums[c]] return ans # Solution 3 class Solution: def countQuadruplets(self, nums: List[int]) -> int: ans, n = 0, len(nums) counter = Counter() for b in range(n - 3, 0, -1): c = b + 1 for d in range(c + 1, n): counter[nums[d] - nums[c]] += 1 for a in range(b): ans += counter[nums[a] + nums[b]] return ans -
func countQuadruplets(nums []int) int { ans, n := 0, len(nums) for a := 0; a < n-3; a++ { for b := a + 1; b < n-2; b++ { for c := b + 1; c < n-1; c++ { for d := c + 1; d < n; d++ { if nums[a]+nums[b]+nums[c] == nums[d] { ans++ } } } } } return ans } // Solution 2 func countQuadruplets(nums []int) int { ans, n := 0, len(nums) counter := make([]int, 310) for c := n - 2; c > 1; c-- { counter[nums[c+1]]++ for a := 0; a < c-1; a++ { for b := a + 1; b < c; b++ { ans += counter[nums[a]+nums[b]+nums[c]] } } } return ans } // Solution 3 func countQuadruplets(nums []int) int { ans, n := 0, len(nums) counter := make([]int, 310) for b := n - 3; b > 0; b-- { c := b + 1 for d := c + 1; d < n; d++ { if nums[d] >= nums[c] { counter[nums[d]-nums[c]]++ } } for a := 0; a < b; a++ { ans += counter[nums[a]+nums[b]] } } return ans }