“This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

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 the 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 the 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 = = 5Copy the code

Note:

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

parsing

(a, b, c, d); (b, c, d); (c, d);

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

The most direct way is to use violence, the idea is as follows:

  • Initialize the counter result to 0
  • Use the built-in function function function digit (nums, 4) to find all combinations possible and then iterate over all combinations to determine if cb[0] + CB [1] + CB [2] == CB [3]. If cb[0] + CB [1] + CB [2] == cb[3], the result counter will be incremented by one
  • Result is returned at the end of traversal

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 the code

The results

Each node in the linked list has long links to the node. Memory Usage: Submissions in Python online submissions for Count Special Quadruplets.Copy the code

parsing

Alternatively, you can use a four-level loop to find the combination of all four indexes to find the quaternion that satisfies the problem. This is also a violent solution, but it is written differently and runs with similar results.

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 the code

The results

Each node in the linked list has long links to the node. Memory Usage: Submissions in Python online submissions for Count Special Quadruplets.Copy the code

parsing

Nums [a] + nums[b] == nums[d] -nums [c] + nums[b] == nums[d] -nums [c] + nums[a] + nums[b] + nums[c] Time complexity can be reduced to O(n^2), the performance improvement is huge!!

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 the code

The results

Long Quadruplets in the linked list. Memory Usage: Submissions in Python online submissions for Count Special Quadruplets.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation