leetcode-mid-array-31 three sum-NO

my code: time limited

 1 def threeSum(nums):
 2         """
 3         :type nums: List[int]
 4         :rtype: List[List[int]]
 5         """     
 6         def twoSum(a,b,c):
 7             if a + b + c == 0:
 8                 return True
 9             else:
10                 return False
11             
12         res = []
13         for i in range(len(nums)-2):
14             a = nums[i]
15             for j in range(i+1,len(nums)-1):
16                 b = nums[j]
17                 k = j +1
18                 #print(i,j,k,a,b,nums[k])
19                 while k < len(nums):
20                     print(a,b,nums[k])
21                     if twoSum(a,b,nums[k]) :
22                         print('....',a,b,nums[k])
23                         temp = [a,b,nums[k]]
24                         temp.sort()
25                         print('...temp',temp)
26                         if temp not in res:
27                             res.append(temp)
28                         print('....res',res)
29                     k += 1   
30         return res

思路：

1、时间复杂度n*n

排序 ( WT1：为什么要排序？）-》构建字典记录value：次数-》两层循环，其中不断不判断第三个数是不是也等于两层循环的值（用到dic的记录次数）

 1 class Solution(object):
 2     
 3     '''
 4     O(n^2)时间复杂度
 5     
 6     '''
 7     def threeSum(self, nums):
 8         """
 9         :type nums: List[int]
10         :rtype: List[List[int]]
11         """
12         result = []
13         num_cnt_dict = {}
14         
15         for num in nums:
16             num_cnt_dict[num] = num_cnt_dict.get(num, 0) + 1
17             
18         if 0 in num_cnt_dict and num_cnt_dict[0] >= 3:
19             result.append([0, 0, 0])
20         
21         nums = sorted(list(num_cnt_dict.keys()))
22         
23         for i, num in enumerate(nums):
24             for j in nums[i+1:]:
25                 if num * 2 + j == 0 and num_cnt_dict[num] >=2:
26                     result.append([num, num, j])
27                 if j * 2 + num == 0 and num_cnt_dict[j] >= 2:
28                     result.append([j, j, num])
29                 
30                 diff = 0 - num - j
31                 if diff > j and diff in num_cnt_dict:
32                     result.append([num, j, diff])
33         return result

注意，以下的方式就会超时，可能是因为list和dict.keys()的检索查找方式不同

                if diff > b and diff in nums:  #要注意>b，才能不和前面的if重合
                    res.append([a,b,diff])
        return res

2、n*m 其中n+m=len(nums)

构建dict -》不排序，将dic的keys分为正数和负数-》两层for循环

注意下面这一行：是因为filter得到的是有序递增数列！！！！！！！所以当diff小于a时，说明当i=diff时候，由于不满足这个条件，还没有把[a,b,diff]放入最后结果

if diff<a or diff>b:
　　 res.append([a,b,diff])

 1 class Solution(object):
 2     
 3     '''
 4     O(n^2)时间复杂度
 5     
 6     '''
 7     def threeSum(self, nums):
 8         """
 9         :type nums: List[int]
10         :rtype: List[List[int]]
11         """
12         res = []
13         dic = {}
14         for item in nums:
15             dic[item] = dic.get(item,0) + 1   
16         if 0 in dic and dic[0] >= 3: 
17             res.append([0,0,0]) #为什么这个要单独列出来 -》因为除了这种情况，for循环中不会再出现三个数相等且和为0的情况
18         #nums = sorted(list(dic.keys())) 
19         neg = list(filter(lambda x:x<0,dic.keys()))
20         pos = list(filter(lambda x:x>=0,dic.keys()))
21         for a in neg:
22             for b in pos:#为什么j的有边界不是len(nums)-1 -》因为可能会存在第三个数巧合和nums[j]相等
23                 diff  = 0 - a - b
24                 if diff in dic:
25                     if diff in (a,b) and dic[diff] >= 2: 
26                         res.append([a,b,diff])
27                     if diff<a or diff>b:
28                         res.append([a,b,diff])
29         return res