使用python的三和问题无法满足所有情况

Question

我试图在dictionaries的帮助下解决著名的[Threesum][1]问题。总体思路是，在匹配或不匹配的情况下，只访问一次元素就将元素添加到字典中，这样就不会两次使用同一元素进行相加和比较。

代码如下:

def threeSum(nums):
nums.sort()
print(nums)
res = []
d = {}
counter = 1
for i in range(len(nums) - 1):
if i not in d.values() and nums[i] not in d.keys():
start = i + 1
end = len(nums) - 1
while start < end:
if (nums[i] + nums[start] + nums[end] == 0):
res.append([nums[i], nums[start], nums[end]])
print([nums[i], nums[start], nums[end]])
start += 1
end -= 1
i += 1
d[nums[i]] = i
d[nums[start]] = start
d[nums[end]] = end
elif (nums[i] + nums[start] + nums[end] > 0):
end -= 1
d[nums[end]] = end
i += 1
d[nums[i]] = i
d[start] = start
d[end] = end
return res

在以下两种情况下作为输入可以正常工作:

list = [-1, 0, 1, 2, -1, -4]
list1 = [0, 0, 0]  

list2 = [1, 2, -2, -1]  

返回如下输出:

[[-1, -1, 2]]  

是不正确的。它应该返回一个空白列表。我哪里做错了?我只想借助字典的帮助，如果可能的话，用非常外行的术语来解决这个问题……

任何帮助都是非常感谢的……

Answer 1

字典实现:

class Solution(object):
def threeSum(self, nums):
length=len(nums) 
res=[]       
dic=dict()
nums.sort()  #Sorted the nums Time- O(NlogN)

for i in range(length):
dic[nums[i]]=i
#print(dic)
i=0
while i<length and nums[i]<=0:  #Run the while loop till i<length and nums[i] is less than or equal to zero 
target=-(nums[i])     
end=length
j=i+1    # We have converted the question to 2-sum problem now just implement 2-sum.
while j<end:
reside=target-nums[j]
if reside in dic and dic[reside]>j:                            
res.append([nums[i],nums[j],reside])
end=dic[reside]
j=dic[nums[j]]+1             
i=dic[nums[i]]+1
return res