您现在的位置是：首页 > Python

当前栏目

[Leetcode][python]4Sum

2023-03-02 11:47:58 时间

## 题目大意 ##

给出数组，找出四个数组合等于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

猜你喜欢

生信爱好者周刊（第 44 期）：为何动物的寿命差异那么大？
安装 openwrt 软路由系统教程
生信爱好者周刊（第 45 期）：读博还是择业？
太占CPU电脑太卡？教你关闭Win11内存压缩
生信爱好者周刊（第 46 期）：你的苹果M系列芯片电脑跑生信顺利么？
Python项目中正确读取写入配置的方式
使用Python轻松获取Binance历史交易
虚拟机 VMware Workstation PRO_v16.2.2_正式版
良心推荐！Python爬虫高手必备的8大技巧！
太好用了，这个更人性化的正则库 -- Humre
Java中自定义扩展Swagger的能力，自动通过枚举类生成参数取值含义描述的实现策略
有了这十二个电子书资源， 99%的书都可以找到
生信爱好者周刊（第 47 期）：RStudio 改名 Posit
面试20K的职位必须要熟悉的Java线程池面试题
智慧学校 - 智慧数字化方式介绍
智能家居 - 智慧数字化方式介绍
用 Python 画如此漂亮的专业插图？简直 So easy！
智慧企业 - 智慧数字化方式介绍
生信爱好者周刊（第 48 期）：人生不能只有一个支点
用Python制作我的核酸检测日历

zl程序教程

当前栏目

[Leetcode][python]4Sum

相关文章