[Leetcode][python]4Sum

谁践踏了优雅 2022-06-10 06:23 80阅读 0赞

## 题目大意 ##

给出数组，找出四个数组合等于target数

## 解题思路 ##

### 双指针 ###

用双重循环，比3Sum多循环一重，当然最后还是归结到双指针2Sum问题。

### hash表 ###

来自：[博客][Link 1]  
需要用到哈希表的思路，这样可以空间换时间，以增加空间复杂度的代价来降低时间复杂度。

首先建立一个字典dict，字典的key值为数组中每两个元素的和，每个key对应的value为这两个元素的下标组成的元组，元组不一定是唯一的。

如对于num=\[1,2,3,2\]来说，dict=\{3:\[(0,1),(0,3)\], 4:\[(0,2),(1,3)\], 5:\[(1,2),(2,3)\]\}。这样就可以检查target-key这个值在不在dict的key值中，如果target-key在dict中并且下标符合要求，那么就找到了这样的一组解。

由于需要去重，这里选用set()类型的数据结构，即无序无重复元素集。最后将每个找出来的解(set()类型)转换成list类型输出即可。

**这种思路请参考上述博客，下方均为3Sum变体，不是上述方法的实现**

## 代码 ##

### 双指针（未用dict） ###

双指针在不用dict的情况下也能通过。

class Solution(object):
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            resultList = []
            nums.sort()
            for num1 in range(0, len(nums)-3):
                for num2 in range(num1 + 1, len(nums)-2):
                    num3 = num2 + 1
                    num4 = len(nums) -1
                    while num3 != num4:
                        summer = nums[num1] + nums[num2] + nums[num3] + nums[num4]
                        if summer == target:
                            list_temp = [nums[num1],nums[num2],nums[num3],nums[num4]]
                            if list_temp not in resultList:
                                resultList.append(list_temp)
                            num3 += 1
                        elif summer > target:
                            num4 -= 1
                        else:
                            num3 += 1
            return resultList

### 双指针（用dict） ###

这里改为dict存储，用空间换时间，结果执行1100ms，比上面的还要多出1000ms，心痛到窒息。

class Solution(object):
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            resultDict = {}
            result = []
            nums.sort()
            for num1 in range(0, len(nums)-3):
                for num2 in range(num1 + 1, len(nums)-2):
                    num3 = num2 + 1
                    num4 = len(nums) -1
                    while num3 != num4:
                        summer = nums[num1] + nums[num2] + nums[num3] + nums[num4]
                        if summer == target:
                            list_temp = [nums[num1],nums[num2],nums[num3],nums[num4]]
                            list_str = str(list_temp)
                            if list_str not in resultDict:
                                resultDict[list_str] = list_temp
                            num3 += 1
                        elif summer > target:
                            num4 -= 1
                        else:
                            num3 += 1
            for value in resultDict.values():
                result.append(value)
            return result

### hash表 ###

200ms

class Solution(object):
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            numLen, res, num_dict = len(nums), set(), {}
            if numLen < 4: 
                return []
            nums.sort()
            for p in range(numLen):  # 存储hash表
                for q in range(p+1, numLen): 
                    if nums[p]+nums[q] not in num_dict:
                        num_dict[nums[p]+nums[q]] = [(p,q)]
                    else:
                        num_dict[nums[p]+nums[q]].append((p,q))
                    # print num_dict
            for i in range(numLen):
                for j in range(i+1, numLen-2):
                    T = target-nums[i]-nums[j]
                    if T in num_dict:
                        for k in num_dict[T]:
                            if k[0] > j: res.add((nums[i],nums[j],nums[k[0]],nums[k[1]]))
            return [list(i) for i in res]

## 总结 ##

优化：可以用一些判断来加速，比如枚举第一个数的时候  
nums\[i\] + nums\[i + 1\] + nums\[i + 2\] + nums\[i + 3\] > target: break  
这是当前能凑齐的最小的4个数，比target后面都不用做了  
nums\[i\] + nums\[n – 3\] + nums\[n – 2\] + nums\[n – 1\] < target: continue  
这是当前凑齐的最大的4个数，比target小，说明第一个数不够大

[Link 1]: http://www.cnblogs.com/zuoyuan/p/3699384.html