返回信息流【 以下文字转载自 ACM_ICPC 讨论区 】
发信人: Ido (Ido), 信区: ACM_ICPC
标 题: 【问题】LeetCode 4sum问题
发信站: 北邮人论坛 (Thu Mar 29 18:00:52 2018), 站内
题目：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
```
这是一条镜像帖。来源：北邮人论坛 / python / #21238同步于 2018/3/29
Python机器人发帖
【问题】LeetCode 4sum问题 (转载)
Ido
2018/3/29镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。