本文共 4609 字，大约阅读时间需要 15 分钟。

题目描述

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]]

Example 2:

Input: nums = []Output: []

Example 3:

Input: nums = [0]Output: []

Constraints:（限制）

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

思路分析

• 注意：

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

暴力破解：

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

• 疑问：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))

测试结果

• 果不其然运行时间超出限制，自己写的时候就是磕磕绊绊，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，然后在逐项加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

分析与总结

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

>>>seq = ['one', 'two', 'three']>>> for i, element in enumerate(seq):...     print i, element... 0 one1 two2 three

转载地址：http://hggpb.baihongyu.com/