# leetcode 1995. Count Special Quadruplets（python）

2022-01-31 13:33:26

「 This is my participation 11 The fourth of the yuegengwen challenge 13 God , Check out the activity details ：2021 One last more challenge

### describe

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], and
• a < 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.
Copy code ``````

Example 2:

``````Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].
Copy code ``````

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
Copy code ``````

Note:

``````4 <= nums.length <= 50
1 <= nums[i] <= 100
Copy code ``````

### analysis

According to the meaning , Give an example from 0 Start indexing the list nums , The title requires us to return different quads ( a , b , c , d ) The number of , bring ：

• nums[a] + nums[b] + nums[c] == nums[d]
• a < b < c < d

The most direct way is to use violent solutions , Ideas as follows ：

• Initialize counter result by 0
• Use built-in functions combinations(nums, 4) Find all the quaternion combinations , Then traverse all combinations to determine whether they meet cb + cb + cb == cb , If yes, the counter result Add one
• Return after traversal result

``````class Solution(object):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for cb in combinations(nums, 4):
if cb + cb + cb == cb:
result += 1
return result

Copy code ``````

### Running results

``````Runtime: 1780 ms, faster than 9.01% of Python online submissions for Count Special Quadruplets.
Memory Usage: 13.3 MB, less than 74.59% of Python online submissions for Count Special Quadruplets.
Copy code ``````

### analysis

In addition, four layers of circulation can be used , Look for the combination of all four indexes to find the quaternion combination that meets the meaning of the question , This is also a violent solution , It's just written differently , The result of running is similar to the above .

``````class Solution(object):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for i in range(len(nums)-3):
for j in range(i+1, len(nums)-2):
for k in range(j+1, len(nums)-1):
for l in range(k+1, len(nums)):
if nums[i]+nums[j]+nums[k] == nums[l]:
result += 1

return result

Copy code ``````

### Running results

``````Runtime: 1588 ms, faster than 37.70% of Python online submissions for Count Special Quadruplets.
Memory Usage: 13.4 MB, less than 74.59% of Python online submissions for Count Special Quadruplets.
Copy code ``````

### analysis

After reading the forum, the great God used the dictionary solution, which is very clever , Mainly used nums[a] + nums[b] == nums[d] - nums[c] This equation , take nums[a] + nums[b] Save in dictionary , Just traverse c and d The index of , The time complexity can be reduced to O(n^2) , The performance improvement is too great ！！

``````class Solution(object):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
res = 0
d = defaultdict(int)
d[nums + nums] = 1
for i in range(2, n - 1):
for j in range(i + 1, n):
res += d[nums[j] - nums[i]]
for j in range(i):
d[nums[i] + nums[j]] += 1
return res
Copy code ``````

### Running results

``````Runtime: 48 ms, faster than 99.18% of Python online submissions for Count Special Quadruplets.
Memory Usage: 13.3 MB, less than 93.44% of Python online submissions for Count Special Quadruplets.
Copy code ``````