Leetcode——3Sum（解决问题的思路，参考他人的代码的优化，以及错误的解决方式）_leedcode 3sum

题目描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

现给一个n个整数的数组，找找看其中有没有三个数加起来为0。找到其中所有的不同的所有组，每组由三个数构成，并且三个数之和为0

Note:

The solution set must not contain duplicate triplets.

最右的结果一定是没有的重复组合的集合

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
1
2

Example 2:

Input: nums = []
Output: []
1
2

Example 3:

Input: nums = [0]
Output: []
1
2

Constraints:（限制）

0 <= nums.length <= 3000，数组的长度是在3000个以内
-105 <= nums[i] <= 105，数组的元素大小在±105之间
1
2

思路分析

• 注意：

  • 不能将列表转集合，消除所有的相同的元素，相同的元素也可相加和为0，如1，1，-2
  • 确保输入的列表有三个及以上的元素的，否则没有办法构成的集合

暴力破解：

*三种循环，列出所有的三元素组合，判定是否相加为0
* 判定最后的组成的组合是否在集合中，不在就加入
1
2

• 疑问：python中如果列表的元素相同，但是位置不同，算是同一个列表吗？
• 解答：首先列表不能够作为集合的元素，集合的数据元素必须是可哈希的不可变的数据类型，列表是可变的数据类型，不可采用。如果换成元组，顺序不同，仍就算是不同的元素。所以不可取，要在组成元组之前，将其中的元素进行排序。

代码实现

python——暴力法

class Solution(object):
    def threeSum(self, nums):
        result = set()
        result2 = list()
        if len(nums)>=3:
              for i in range(len(nums)-2):
                  for j in range(i + 1,len(nums)- 1):
                      for k in range(j + 1,len(nums)):
                          if(nums[i] + nums[j] + nums[k] == 0):
                              result.add(tuple(sorted((nums[i],nums[j],nums[k]))))
              for i in range(len(result)):
                  result2.append(list(result.pop()))
              return result2
        else:
              return []

if __name__ == '__main__':
    test = Solution()
    nums = [-1,0,1,2,-1,-4]
    print(type(nums))
    print(test.threeSum(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试结果

• 果不其然运行时间超出限制，自己写的时候就是磕磕绊绊，python刚刚用起来，之前学的忘得差不多了。
• 不过说实话，如果这个方法我用C语言来实现，不用写了，太多了，光是集合的去除相同元素就很难了。
• 遇到的问题

  • python中使用类创建对象，要在类名后面加上括号，不加会出现如下的异常。没有对对象进行初始化。

  • 集合中的元素有要求，必须是不可变的数据结构，元素，字符串等；不可以以可变的数据结构作为其中的元素，如列表，字典。

  • 元素相同，但是顺序不同的元组仍旧是不同的元组

改进——如何减少遍历所化的时间和的次数

• 将所有的数字进行排序，分成两个数组，正数和负数，零单独算。最终能构成零，除了三个零的极端情况，一定有一个正数一个负数。
• 从正数和负数分别取一个出来，找出所有的组合，然后在根据两者之和，在原来的数组中寻找
• 最多是3000个元素，终究总共有15000*15000种组合，根本不切实际。每一种组合还要遍历完整的数组一次，不划算。

参考教程

解决办法

• 针对有数字重复：将列表进行排序，相同的数字经过排序过后一定是在一起的，所以可以直接跳过
• 针对的重复的组合：固定位置，将3Sum转成2Sum的，同时在2Sum中，避免重复，如果左右边界点移动之后都是相同的，那就跳过

图示

代码实现

def threeSum(self,nums):
    result = list()
    if len(nums) >= 3:
        # 将原来的数组进行排序，屏蔽重复的数字的影响
        nums.sort()
        # 分为两重遍历，最外侧遍历是确定三数相加的第一个位置，并将问题简化为2Sum，第二层遍历是确定解决2Sum的问题
        i = 0
        while i < len(nums):
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[left] + nums[right] == 0 - nums[i]:
                    result.append([nums[i], nums[left], nums[right]])

                    temp = 1
                    while left + temp < len(nums) and nums[left + temp] == nums[left]:
                        temp += 1
                    left = left + temp

                    temp = 1
                    while nums[right - temp] == nums[right]:
                        temp += 1
                    right = right - temp
                elif nums[left] + nums[right] > 0 - nums[i]:
                    temp = 1
                    while nums[right - temp] == nums[right]:
                        temp += 1
                    right = right - temp
                else:
                    temp = 1
                    while left + temp < len(nums) and nums[left + temp] == nums[left]:
                        temp += 1
                    left = left + temp
            temp = 1
            while i + temp < len(nums) and nums[i + temp] == nums[i]:
                temp += 1
            i += temp
        return result
    else:
        return []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

运行结果

分析与总结

• 在实际操作中，注意数组的越界问题，无论是左边界点还是右边界点，都要进行控制
• 越过所有相同的数据方法，基本步骤设置为1，然后在逐项加1，获取最后的结果。

参考代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, a in enumerate(nums):
            if i > 0 and a == nums[i - 1]:
                continue
            # 迭代之后，先判定和之前的值是否相同，如果相同直接跳过，进行下一次循环。
            
            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                # 如果遇见的是相同的，没有必要在进行判定是否相同，相同并不会起到缩小或者增加的作用
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
                    # 没有必要两边同时缩小，仅仅需要改变一边，另外一边会自动平衡
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

分析与总结

• enumerate（）：将一个可遍历的数据对象组合为一个索引序列，同时列出数据和数据下标，一般使用在for循环中
  • enemurate（可以遍历的对象，开始遍历的位置）

>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
... 
0 one
1 two
2 three
1
2
3
4
5
6
7