Skip to content

Instantly share code, notes, and snippets.

@shanehou
Last active August 29, 2015 14:17
Show Gist options
  • Save shanehou/2da63359ba70dd8dad7d to your computer and use it in GitHub Desktop.
Save shanehou/2da63359ba70dd8dad7d to your computer and use it in GitHub Desktop.
看起来并没有重复,但提示Output Limit Exceeded
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if len(num) < 3:
return []
threes = []
countMap = dict()
for i in num:
if i in countMap:
countMap[i] += 1
else:
countMap[i] = 1
for i in range(len(num)):
exclude = set()
target = 0 - num[i]
if num[i] not in countMap:
continue
countMap[num[i]] -= 1
for j in range(i+1, len(num)):
if num[j] in exclude or target - num[j] in exclude or num[j] not in countMap:
continue
if countMap.get(target - num[j], 0) > 0:
if target == 2 * num[j] and countMap.get(num[j], 0) <= 1:
continue
exclude.add(target - num[j])
exclude.add(num[j])
threes.append(sorted([num[i], num[j], target - num[j]]))
if num[i] in countMap:
del countMap[num[i]]
return threes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment