同样的思路，计算时间确实别人的百倍

最近在在刷 LeetCode，已经刷到 15 题了，但是在 15 题这卡住了，特来请教。以下是我的代码

class Solution: def threeSum(self, nums): negative = [] negative_again = [] positive = [] positive_again= [] zero = [] answer = [] m, n = 0, 0 for value in nums: if value < 0: if -value not in negative: negative.insert(0, -value) elif -value not in negative_again: negative_again.append(-value) elif value > 0: if value not in positive: positive.append(value) elif value not in positive_again: positive_again.append(value) else: zero.append(value) positive.sort() negative.sort() if len(zero) > 2: answer.append([0, 0, 0]) if len(positive) == 0 or len(negative) ==0: return answer for i in negative: # [i, 0, -i] # 第一个 for n = 1 + n if i > positive[-1]: break for j in negative[n:]: # [i, j, -i-j] ij = i + j #print(i, i, ij) if ij > positive[-1]: break if ij in positive: pre_answer = [-j, -i, ij] answer.append(pre_answer) for i in positive: # 第二个 for m = m + 1 if i > negative[-1]: break for j in positive[m:]: ij = i + j if ij > negative[-1]: break if ij in negative: pre_answer = [i, j, -ij] answer.append(pre_answer) if len(zero) > 0: for i in positive: if i in negative: answer.append([-i, 0, i]) for i in negative_again: if (i + i) in positive: pre_answer = [-i, -i, i+i] answer.append(pre_answer) for i in positive_again: if (i + i) in negative: pre_answer = [ -i-i, i, i] answer.append(pre_answer) return answer 

这里是第一名的代码（我借鉴他的思路写的，但是速度差了 100 倍）

 class Solution: def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ out = [] zero = 0 positive, negative = {}, {} p_max = 0 n_min = 0 import itertools if not nums: return out for i in nums: if i > 0: positive[i] = positive.get(i, 0) + 1 if i > p_max: p_max = i elif i < 0: negative[i] = negative.get(i, 0) + 1 if i < n_min: n_min = i else: zero += 1 if len(positive) == 0 or len(negative) == 0: if zero > 2: out.append([0, 0, 0]) return out p = sorted(positive.keys()) for i in range(len(p)): # 第一个 for if p[i] > -n_min: break for j in range(i+1, len(p)): s = p[i]+p[j] if s > -n_min: break if -s in negative: out.append([p[i], p[j], -s]) if positive[p[i]] >= 2: if -(p[i]*2) in negative: out.append([p[i], p[i], -(p[i]*2)]) n = sorted([-k for k in negative]) for i in range(len(n)): # 第二个 for if n[i] > p_max: break for j in range(i + 1, len(n)): s = n[i] + n[j] if s > p_max: break if s in positive: out.append([-n[i], -n[j], s]) if negative[-n[i]] >= 2: if (n[i]*2) in positive: out.append([-n[i], -n[i], (n[i]*2)]) if zero > 0: for i in positive: if -i in negative: out.append([i,0,-i]) if zero > 2: out.append([0, 0, 0]) return out 

我导入了 timeit，计算了一下时间，差别在 for 循环的块里（就是我注释的两个 for 循环），排查了两晚上，也没找到答案。