Leetcode No.18 四数之和

一、题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

二、解题思路

最朴素的方法是使用四重循环枚举所有的数组，然后使用哈希表进行去重操作，得到不包含重复四元组的最终答案。假设数组的长度是 n，则该方法中，枚举的时间复杂度为 O(n^4)，去重操作的时间复杂度和空间复杂度也很高，因此需要换一种思路。

将数组中的两两元素加起来，放在一个哈希表中，key为加和，value为两两元素的下标

双层for循环遍历数组，再加一层循环遍历哈希表，当nums[i]+num[j]+哈希表的key(两两元素的和)=target，将相应的下标 i,j,哈希表的value(两两元素的下标)，放入结果表。

三、代码

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        d={}
        for i