leetcode 1995. Count Special Quadruplets（python）

「 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[0] + cb[1] + cb[2] == cb[3] , If yes, the counter result Add one
• Return after traversal result

answer

class Solution(object):
    def countQuadruplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for cb in combinations(nums, 4):
            if cb[0] + cb[1] + cb[2] == cb[3]:
                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 .

answer

class Solution(object):
    def countQuadruplets(self, nums):
        """
        :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 ！！

answer

class Solution(object):
    def countQuadruplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        res = 0
        d = defaultdict(int)
        d[nums[0] + nums[1]] = 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 

Original link ：leetcode.com/problems/co…

Your support is my greatest motivation