leetcode题解第18题 4Sum（四数之和）

短命女 2022-03-01 10:08 160阅读 0赞

跟第15题、第16题比较相似的一道题，题目大意是说：

> 给定一个包含n个整数的数组nums和一个整数target，从数组中找出所有不重复的四个数相加等于0的组合。  
> 注意，仅字典序不同的、包含数字相同的四元组被认为是重复的，只能保留其中一个。

样例输入：

> nums = \[1, 0, -1, 0, -2, 2\]  
> target = 0

样例输出：

> \[  
> \[-1, 0, 0, 1\],  
> \[-2, -1, 1, 2\],  
> \[-2, 0, 0, 2\]  
> \]

题目链接：[https://leetcode.com/problems/4sum/][https_leetcode.com_problems_4sum]

解题思路：

最简单的思路当然是四层循环啦，但不用试，估计也会爆炸=。=

怎么优化呢？对，还是二分，这几道题一直在考二分orz…

1.  总共n个数，我们可以把它们两两相加，产生一个新的列表。且列表中的每个元素不止保存两个数的和，还要保存这两个数的下标，可以通过类（python）或结构体（c/c++）来实现。
2.  新的列表我们给它起个名字，比方说就叫sumnums。对sumnums进行排序，方便后面使用二分查找。
3.  枚举sumnums中的元素a，使用二分查找sumnums中值为target-a的元素。  
    3.1 如果找到了，那么从这个坐标向左右两边遍历，找到所有值等于target-a的元素。  
    3.2 如果没找到，那么开始枚举下一个数据。
4.  对于3.1中获取到的所有值为target-a的元素，判断它的构成它的两个数的下标是否和a的两个下标有交集。有交集则跳过，无交集则四个下标对应的数字就是一种符合条件的组合。
5.  对所有结果进行去重，并返回结果列表即可。

样例代码：

from collections import namedtuple
    
    SumNum = namedtuple('SumNum', 'sum,x,y,pos_x,pos_y')
    
    
    class Solution:
        result = set()
    
        def bin_search(self, nums, left, right, target):
            """ 二分查找，找到就返回相应坐标，找不到就返回-1 :param nums: :param left: :param right: :param target: :return: """
            while left <= right:
                mid = (left + right) >> 1
                x: SumNum = nums[mid]
                if x.sum == target:
                    return mid
                elif x.sum > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1
    
        def find_equal(self, cur_pos, find_pos, sumnums):
            """ 从find_pos向左右两边延伸，处理每一个与sumnums[find_pos].sum值相等的元素 判断处理到的元素与sumnums[cur_pos]的两个坐标是否有交集，有则放弃，无则加入结果集 :param cur_pos: :param find_pos: :param sumnums: :return: """
            num = sumnums[find_pos].sum
            cur_sumnum = sumnums[cur_pos]
            # 向左延伸，处理所有值和num相等的元素
            left_pos = find_pos
            while left_pos >= 0 and sumnums[left_pos].sum == num:
                tmp_sumnum = sumnums[left_pos]
                # 判断坐标是否有重复，因为原始列表中的每个数字只能使用一次，所以如果有重复就不是正确答案
                if cur_sumnum.pos_x != tmp_sumnum.pos_x and cur_sumnum.pos_x != tmp_sumnum.pos_y and cur_sumnum.pos_y != tmp_sumnum.pos_x and cur_sumnum.pos_y != tmp_sumnum.pos_y:
                    # 如果没有重复，将排序后的四元组加入到结果集中（这么做是为了避免不同字典序产生的重复问题）
                    self.result.add(tuple(sorted([cur_sumnum.x, cur_sumnum.y, tmp_sumnum.x, tmp_sumnum.y])))
                left_pos -= 1
            # 向右延伸，处理方法同上
            right_pos = find_pos + 1
            while right_pos < len(sumnums) and sumnums[right_pos].sum == num:
                tmp_sumnum = sumnums[right_pos]
                if cur_sumnum.pos_x != tmp_sumnum.pos_x and cur_sumnum.pos_x != tmp_sumnum.pos_y and cur_sumnum.pos_y != tmp_sumnum.pos_x and cur_sumnum.pos_y != tmp_sumnum.pos_y:
                    self.result.add(tuple(sorted([cur_sumnum.x, cur_sumnum.y, tmp_sumnum.x, tmp_sumnum.y])))
                right_pos += 1
    
        def fourSum(self, nums, target: int):
            # 清空结果集
            self.result.clear()
            # 排序
            nums = sorted(nums)
            # 计算两两之和，作为新的列表
            sumnums = [SumNum(nums[i] + nums[j], nums[i], nums[j], i, j) for i in range(len(nums)) for j in
                       range(i + 1, len(nums))]
            # 排序
            sumnums = sorted(sumnums)
            # 枚举新列表中的每个元素
            for i in range(len(sumnums)):
                # 在新列表中查找target-sumnums[i].sum
                pos = self.bin_search(sumnums, i + 1, len(sumnums) - 1, target - sumnums[i].sum)
                # 如果找到了
                if pos != -1:
                    # 就进一步进行处理，并加入到结果集中
                    self.find_equal(i, pos, sumnums)
            return list(self.result)

转载请注明出处：[https://blog.csdn.net/aaronjny/article/details/88736904][https_blog.csdn.net_aaronjny_article_details_88736904]

[https_leetcode.com_problems_4sum]: https://leetcode.com/problems/4sum/
[https_blog.csdn.net_aaronjny_article_details_88736904]: https://blog.csdn.net/aaronjny/article/details/88736904