【Leetcode】【python】4Sum

题目大意

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

解题思路

双指针

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

hash表

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

首先建立一个字典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小，说明第一个数不够大