leetcode刷题日记-1995. 统计特殊四元组

leetcode刷题日记-1995. 统计特殊四元组

• 题目描述：
  给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
  nums[a] + nums[b] + nums[c] == nums[d] ，且a < b < c < d

• 示例：
  输入：nums = [1,2,3,6]
  输出：1
  解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6
  
  输入：nums = [3,3,6,4,5]
  输出：0
  解释：[3,3,6,4,5] 中不存在满足要求的四元组。
  
  输入：nums = [1,1,1,3,5]
  输出：4
  解释：满足要求的 4 个四元组如下：
  (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

  由于之前刷过二数之和、三数之和、四数之和的题目，乍一看这道题目是简单有点难以置信，总不能考个四重循环吧？？？结果尝试着试了一下，还真是考四重循环来进行枚举，顿时感觉变Low了。那么为什么要写这篇博客呢？
  虽然这个题目很简单，考点也很没意思，但是优化过程很好玩，我们通过一个思路将时间复杂度从O(n4)，降到O(n3)，最后再降到O(n2)，这个过程还是很有意思的。

• 首先我们先上最简单最暴力的解法，代码如下，这个应该没什么好说的，就是一个四重循环，时间复杂度妥妥的O(n4)。

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        """
        给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, 
        c, d) 的 数目.其中nums[a] + nums[b] + nums[c] == nums[d]，且a < b < c < d
        >>>
        >>>self.countQuadruplets([1,2,3,6])
        >>>1
        """
        n = len(nums)
        ans = 0
        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

• 首先我们定一个小目标，如果将时间复杂度降低到O(n3)。我们观察nums[a] + nums[b] + nums[c] == nums[d] ，且a < b < c < d，如果nums[d] 有重复，为k，那么ans += k，我们就可以想到，我们可以用一个Hash来存储nums[d] 的值，由于d的取值是(c+1, n)，所以我们只要确定c，同时，倒序遍历c，这样就保证所有的d都满足条件，并将nums[d]加入hash表（这里的时间复杂度为O(1)，因为我们每次记录nums[c+1]的值即可），同时，在确定a和b，就可以完成所有的循环，所以该思路的时间复杂度为O(n3)，代码如下：

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        """
        给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, 
        c, d) 的 数目.其中nums[a] + nums[b] + nums[c] == nums[d]，且a < b < c < d
        >>>
        >>>self.countQuadruplets([1,2,3,6])
        >>>1
        """
        n = len(nums)
        ans = 0
        count = Counter()
        for c in range(n-2, 1, -1):
            count[nums[c+1]] += 1
            for b in range(c-1, 0, -1):
                for a in range(b-1, -1, -1):
                    if (temp := nums[a] + nums[b] + nums[c]) in count:
                        ans += count[temp]
        return ans

• 注：:=是赋值运算法，可以简单理解为=

• 最后再进一步考虑，能不能再降低时间复杂度。我们再度观察公式nums[a] + nums[b] + nums[c] == nums[d] ，这个可以改写成nums[a] + nums[b] == nums[d] -nums[c] ，到这里，可能就发现了一点什么，但是又没有完全发现。我们可以发现，如果我们确认了b，其实就确定了a-(0, b)、c-(b+1, d)，所以只要我们再确定d，就枚举了所有的a、b、c、d，我们通过hash记录nums[d] -nums[c] ，之后在比较nums[a] + nums[b] 的结果是否出现在hash表中，由于hash记录nums[d] -nums[c]和nums[a] + nums[b] 确定是同级循环，因此该思路的时间复杂度为O(n2)，代码如下：（这里的中间值不一定选b，选c也一样，但是一定要在b、c里面选）

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        """
        给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, 
        c, d) 的 数目.其中nums[a] + nums[b] + nums[c] == nums[d]，且a < b < c < d
        >>>
        >>>self.countQuadruplets([1,2,3,6])
        >>>1
        """
        n = len(nums)
        ans = 0
        count = Counter()
        for b in range(n-3, 0, -1):
            for d in range(b+2, n):
                count[nums[d]-nums[b+1]] += 1
            for a in range(b):
                if (temp := nums[a] + nums[b]) in count:
                    ans += count[temp]
        return ans

• 选c的解法：

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        """
        给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, 
        c, d) 的 数目.其中nums[a] + nums[b] + nums[c] == nums[d]，且a < b < c < d
        >>>
        >>>self.countQuadruplets([1,2,3,6])
        >>>1
        """
        n = len(nums)
        ans = 0
        count = Counter()
        for c in range(n-2, 1, -1):
            for d in range(c+1, n):
                count[nums[d]-nums[c]] += 1
            for a in range(c-1):
                if (temp := nums[a] + nums[c-1]) in count:
                    ans += count[temp]
        return ans