【LeetCode刷题笔记（7-1）】【Python】【四数之和】【哈希表】【中等】

四数之和

四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n

a、b、c 和 d 互不相同

nums[a] + nums[b] + nums[c] + nums[d] == target

可以按 任意顺序 返回答案 。

示例 1

• 输入：nums = [1,0,-1,0,-2,2], target = 0
• 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2

• 输入：nums = [2,2,2,2,2], target = 8
• 输出：[[2,2,2,2]]

提示

• 1 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

解决方案1：【四层遍历查找】

对于解决【四数之和】这个问题，一种直观的解法是四层循环枚举所有可能的四元组，然后判断它们的和是否为目标值target，但是这样的时间复杂度是 O(n⁴)，对于较大的数组来说是不可接受的。

解决方案2：【哈希表】+【三层遍历】

在探讨【四数之和】这一算法题之前，我相信许多读者已经对【三数之和】有所涉猎。在【【LeetCode刷题笔记（6-1）】【Python】【三数之和】【哈希表】【中等】】中，我详细介绍了如何设计基于【哈希表】的算法解决【三数之和】问题。

现在，摆在我们面前的是【四数之和】问题，它与【三数之和】在本质上是一样的。因此，我们很自然地会把解决【三数之和】的算法搬过来，在此基础上修改，从而解决【四数之和】问题。

完整代码如下：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        hash_map = {}
        num_idx = 0
        new_nums = []
        for idx, num in enumerate(nums):
            if num not in hash_map:
                hash_map[num] = [num_idx]
                new_nums.append(num)
                num_idx += 1
            else:
            	# 修改1：原数组的任意元素都可以重复至多四次
                if len(hash_map[num]) < 4: 
                    hash_map[num].append(num_idx)
                    new_nums.append(num)
                    num_idx += 1
                else:
                    pass
            
                
        result_list = []  
        n = len(new_nums)
        is_used_results = set()
        # 修改2：两层遍历改用三层遍历
        for i in range(n):  
            for j in range(i+1, n):  
                for k in range(j+1, n):
                    if target -(new_nums[i] + new_nums[j] + new_nums[k]) in hash_map: 
                        for m in hash_map[target -(new_nums[i] + new_nums[j] + new_nums[k])]:  
                            if m == i:
                                continue
                            elif m == j:
                                continue
                            # 修改3：在进行索引去重操作时，多判断一次
                            elif m == k:
                                continue
                            else:
                                sorted_result = tuple(sorted([new_nums[k], new_nums[i], new_nums[j], new_nums[m]]))
                                if sorted_result in is_used_results: 
                                    pass
                                else:
                                    result_list.append([new_nums[k], new_nums[i], new_nums[j], new_nums[m]])  
                                    is_used_results.add(sorted_result)  
  
        return result_list

如果对上面代码的执行逻辑不太熟悉，建议参考一下【【LeetCode刷题笔记（6-1）】【Python】【三数之和】【哈希表】【中等】】中的代码，上面的代码和解决【三数之和】的代码绝大部分是一致的，注释和算法逻辑也在【【LeetCode刷题笔记（6-1）】【Python】【三数之和】【哈希表】【中等】】叙述的非常清楚。

因此，在这篇博客中，我主要叙述一下修改细节。

1. 与【三数之和】问题一样，【四数之和】的原数组nums也会出现冗余的情况。但不一样的是，【四数之和】允许原数组nums的元素重复至多四次，因为存在num*4 = target的情况，而【三数之和】对于除0以外的任意元素，至多重复两次。
   基于这个认知，我们需要修改【原数组去重部分的代码】，使得原数组的任意元素都可以重复至多四次。修改之处在上面的代码已标明。

2. 由于是【四数之和】，因此需要从两层遍历改用三层遍历；

3. 由于是【四数之和】，需要保证四个索引互不相同，因此需要额外多进行一次去重操作。

运行结果：

复杂度分析

• 时间复杂度：O(N³)，其中 N 是新数组new_nums元素的数量。
  • 三层循环遍历新数组 ===> O(N³)
• 空间复杂度：O(N)
  • 需要用哈希表和列表存放新数组 ===> O(N)

结束语

• 亲爱的读者，感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见，因此在这里鼓励您对我们的博客进行评论。
• 您的建议和看法对我们来说非常重要，这有助于我们更好地了解您的需求，并提供更高质量的内容和服务。
• 无论您是喜欢我们的博客还是对其有任何疑问或建议，我们都非常期待您的留言。让我们一起互动，共同进步！谢谢您的支持和参与！
• 我会坚持不懈地创作，并持续优化博文质量，为您提供更好的阅读体验。
• 谢谢您的阅读！