三数之和015 -力扣（双指针+py3)

朴灿烈づ我的快乐病毒、 2022-11-21 14:49 112阅读 0赞

## 1.题目 ##

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

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

示例：

给定数组 nums = \[-1, 0, 1, 2, -1, -4\]，

满足要求的三元组集合为：  
\[  
\[-1, 0, 1\],  
\[-1, -1, 2\]  
\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/3sum

## 2.解法 ##

对于该题直接暴力求解会发现超时，因此改进暴力求解，采用排序加双指针法去解决该题，解法具体要点如下：

1.  特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回\[ \]。
2.  对数组进行排序。
3.  遍历排序后数组：

*  若  n u m s \[ i \] > 0 nums\[i\]>0 nums\[i\]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，同理若 n u m s \[ − 1 \] < 0 nums\[-1\]<0 nums\[−1\]<0，也不可能存在三个数之和等于0，直接返回结果\[ \]。
 *  对于重复元素：跳过，避免出现重复解
 *  令左指针 L=i+1，右指针 R=n-1，当 L<R时，执行循环：  
    \- 当 nums\[i\]+nums\[L\]+nums\[R\]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解  
    \- 若和大于 0，说明 nums\[R\] 太大，R 左移  
    \- 若和小于 0，说明 nums\[L\]太小，L 右移

**复杂度分析**  
时间复杂度： O ( n 2 ) O(n^\{2\}) O(n2)，数组排序 O ( N l o g N ) O(Nlog N) O(NlogN)，遍历数组  O ( n ) O(n) O(n)，双指针遍历  O ( n ) O(n) O(n)，总体  O ( N l o g N ) + O ( n ) ∗ O ( ) ( N l o g N ) + O ( n ) ∗ O ( n ) O(NlogN)+O(n)\*O()(NlogN)+O(n)∗O(n) O(NlogN)\+O(n)∗O()(NlogN)\+O(n)∗O(n)，即为 O ( n 2 ) O(n^2) O(n2)  
空间复杂度：O(1)O(1)  
参考链接：https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/

代码如下：

def threeSum(self, nums: List[int]) -> List[List[int]]:
    
            if len(nums) < 3:
                return []
            nums.sort()
            res = []
            for i, num in enumerate(nums[:-2]):
                if nums[0] > 0 or nums[-1] < 0:
                    break
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                L, R = i + 1, len(nums) - 1
                while L < R:
                    temp = num + nums[L] + nums[R]
                    if temp == 0:
                        res.append([num, nums[L], nums[R]])
    
                        while L < R and nums[L+1] == nums[L]:
                            L = L + 1
                        while L < R and nums[R-1] == nums[R]:
                            R = R - 1
                        L = L + 1
                        R = R - 1
                    elif temp > 0:
                        R = R - 1
                    else:
                        L = L + 1
            return res

注：  
**另外需要注意的一点：Python 中排序函数sort和sorted函数，使用的 Timsort 算法，时间复杂度为 O ( N l o g N ) O(Nlog N) O(NlogN)**

关于sort函数与sorted函数更详细的内容可以看下面这篇博客：  
[https://blog.csdn.net/qq\_38048756/article/details/109464955][https_blog.csdn.net_qq_38048756_article_details_109464955]

[https_blog.csdn.net_qq_38048756_article_details_109464955]: https://blog.csdn.net/qq_38048756/article/details/109464955