返回信息流题目：https://leetcode.com/problems/4sum/description/
我思路是仿照3sum，但对于这个测试实例 nums=[0,0,0,0,0,0] target=0，就是有4个值相同并且恰好这四个值之和就等于target，我写的代码对于这种情况都跳过了，但是不跳过的话又会得到重复的结果，怎么把这种case通过呢？求大佬指点。
另外：对于k-sum问题的时间复杂度是n的k-1次方吗？
代码如下:
```
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res=[]
nums.sort()
for i in range(len(nums)-3):
if nums[i]==nums[i-1] and i>0:
continue
for j in range(i+1,len(nums)-2):
if nums[j]==nums[j-1] and j>i:
continue
l,r=j+1,len(nums)-1
while l<r:
s=nums[i]+nums[j]+nums[l]+nums[r]
if s<target:
l+=1
elif s>target:
r-=1
else:
res.append([nums[i],nums[j],nums[l],nums[r]])
while l<r and nums[l]==nums[l-1]:
l+=1
while l<r and nums[r]==nums[r-1]:
r-=1
l+=1
r-=1
return res
```
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95291同步于 2018/3/29
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】LeetCode 4sum问题
Ido
2018/3/29镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
对，还有类似这种情况我这么写也过不去，nums=[0,0,-1,-1] target=0 如果不考虑空间的话，实在不行就用字典判重了，
【 在 Macaulish64 的大作中提到: 】
: 如果k比较小就分类讨论：有1个数值相同的，有两个数值相同的…………
: 如果k比较大可能得用用组合数学算算重复的
照着你的代码改了两处，就过了：
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res=[]
nums.sort()
for i in range(len(nums)-3):
if nums[i]==nums[i-1] and i>0:
continue
for j in range(i+1,len(nums)-2):
if nums[j]==nums[j-1] and j>i+1: #这里j要从i+2开始判重，
continue
l,r=j+1,len(nums)-1
while l<r:
s=nums[i]+nums[j]+nums[l]+nums[r]
if s<target:
l+=1
elif s>target:
r-=1
else:
res.append([nums[i],nums[j],nums[l],nums[r]])
while l<r and nums[l]==nums[l+1]: # 这里如果是l-1，就会跳过一个数
l+=1
while l<r and nums[r]==nums[r-1]:
r-=1
l+=1
r-=1
return res
import collections
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
dict1 = collections.defaultdict(list)
for i in range(len(nums)-1):
for j in range(i+1,len(nums)):
dict1[nums[i]+nums[j]].append([i,j])
two_sum = dict1.keys()
result = []
visited = set()
for a in two_sum:
if a in visited:continue
if dict1.has_key(target-a):
for index1 in dict1[a]:
for index2 in dict1[target-a]:
if len(set(index1+index2))<4:continue
number = [nums[index] for index in index1 + index2]
number.sort()
if number in result:continue
result.append(number)
visited.add(a)
visited.add(target-a)
return result