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

[getlost]

最近在在刷 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 循环），排查了两晚上，也没找到答案。

[getlost]

https://leetcode-cn.com/problems/3sum/submissions/ 这是 LeetCode 题目。

[wallriding]

这题需要写这么长吗？

[getlost]

@wallriding 刚开始练习，还需要努力学习

[wallriding]

@getlost 你直接看 discussion 里最高票帖子呀

[getlost]

@wallriding 第二段代码是耗时最短的解法，我参考他的解法来做了一次，但是存在疑问，因为用了同样的逻辑，耗时却差了 100 倍，我很疑惑，不知道哪里理解错了。

[Gakho]

试过 copy 第一名的解法直接提交，时间也会出现差了一半以上，说实话对于这个时间我大多数抱着看看就好的心态

[getlost]

@Gakho 我本地试的，同样的参数，他的就是比我快 100 倍，为啥还不知道

[hanbaobao2005]

insert 的效率很差，不建议使用

[getlost]

@hanbaobao2005 学习了，之前没了解过。我导入 timeit 模块，发现我的两个 for 循环占用的时间占总时间的 99%，不太明白为什么？

[hanbaobao2005]

@getlost 替换 insert 试过了么？