[Leetcode][python]4Sum
[Leetcode][python]4Sum
蛮三刀酱
发布于 2019-03-26 16:44:30
发布于 2019-03-26 16:44:30
题目大意
给出数组，找出四个数组合等于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 resulthash表
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小，说明第一个数不够大
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月12日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录