LeetCode题目（Python实现）：三数之和

迈不过友情╰ 2023-07-10 14:13 5阅读 0赞

### 文章目录 ###

*  题目
 *   *  排序 + 双指针法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  分情况讨论法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

**注意**：答案中不可以包含重复的三元组。

**示例** :

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

## 排序 + 双指针法 ##

### 算法实现 ###

class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            n = len(nums)
            res = []
            if n < 3:
                return []
            nums.sort()
            res = []
            for i in range(n):
                if nums[i] > 0:
                    return res
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                L = i + 1
                R = n - 1
                while L < R:
                    sum = -(nums[L] + nums[R])
                    if sum == nums[i]:
                        res.append([nums[i], nums[L], nums[R]])
                        while L < R and nums[L] == nums[L + 1]:
                            L += 1
                        while L < R and nums[R] == nums[R - 1]:
                            R -= 1
                        L += 1
                        R -= 1
                    elif nums[i] > sum:
                        R -= 1
                    else:
                        L += 1
            return res

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 756 ms, 在所有 Python3 提交中击败了89.05%的用户  
**内存消耗** : 16.1 MB, 在所有 Python3 提交中击败了71.74%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n^2)
 *  空间复杂度：O(1)

## 分情况讨论法 ##

### 算法实现 ###

class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            # 初始化result
            result = []
            # 先把nums构造成字典
            counter = collections.Counter(nums)
            # 获取不重复的nums列表
            nums = sorted(counter)
    
            # 先考虑 [i, 0, -i] 的情况
            if counter.get(0, 0) >= 1:
                for i in nums:
                    if i < 0:
                        if counter.get(-i, 0) > 0:
                            result.append([i, 0, -i])
                if counter.get(0, 0) >= 3:
                    result.append([0, 0, 0])
    
            # 再考虑 [i, i, -2i] 的情况
            for i in nums:
                if counter.get(i, 0) >= 2 and counter.get(-2 * i, 0) >= 1 and i != 0:
                    result.append([i, i, -2 * i])
    
            # 再考虑 [i, j, k] 为了避免重复， 规定 i < 0; j > 0; k大于0时比j大 k小于0时比i小
            negative = {
        k: v for k, v in counter.items() if k < 0}
            positive = {
        k: v for k, v in counter.items() if k > 0}
            for i in negative.keys():
                for j in positive.keys():
                    k = - i - j
                    if k < 0:
                        if k > i and k in negative:
                            result.append([i, j, k])
                    elif k > 0:
                        if k > j and k in positive:
                            result.append([i, j, k])
    
            return result

### 执行结果 ###

![在这里插入图片描述][2020030301311022.png]

### 复杂度分析 ###

*  时间复杂度：O(n^2)
 *  空间复杂度：O(1)

## 小结 ##

题目的难点在于去重复解，想了很多办法，例如将分很多情况讨论，将已有组合加入到字典中，但说实话仍然没有解决这个问题，或者是自己没有特别好的思路。最后还是看了解析，学习了先排序再双指针遍历的方法，对其稍加改进，以少量空间换取一定的速度，加快了算法。

之后还看到一个和我开始想法相同分情况的算法，学习了一下他的方法，主要是最后一种情况较难想到实现的方法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303003831632.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[2020030301311022.png]: https://img-blog.csdnimg.cn/2020030301311022.png