Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
这题有多种解法,使用two pointer的解法复杂度是O(n^3)的,枚举前两位,后两位是双指针,这种解法很trival。另外一种解法是使用hashmap先保存两两的pair。
然后采用two sum的解法。值得注意的是two sum那题是数组里所有的数字都不一样,但是这里不一样,pair很多的和值是一样的,数字本身也可能有重复,所以去重非常关键。代码如下:
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not nums or len(nums) < 4:
return []
nums.sort()
res = set()
map = {}
for i in xrange(0,len(nums)):
for j in xrange(i+1, len(nums)):
key = nums[i] + nums[j]
if key not in map:
map[key] = [(nums[i],nums[j],i,j)]
else:
map[key].append((nums[i],nums[j],i,j))
for key, value in map.iteritems():
sub = target - key
if key <= target/2 and sub in map:
for a in value:
for b in map[sub]:
if a[2] != b[2] and a[3]!= b[3] and a[3] != b[2] and a[2]!=b[3]:
res.add(tuple(sorted([a[0],b[0],a[1],b[1]])))
return [list(a) for a in res]
这题个人觉得最坏的时间复杂度是O(n^4)的,数组全部都是target/4的情况,具体还需要再思考,详见一个leetcode讨论和另外一个一亩三分地的帖子,一个很好的解法http://www.cnblogs.com/TenosDoIt/p/3649607.html