当前位置：首页 > news >正文

【双指针】专题：LeetCode 15题解——三数之和

news 来源：原创 2025/6/19 17:59:56

三数之和

一、题目链接
二、题目
三、题目解析
四、算法原理
- 解法一：排序 + 暴力枚举 + 利用set去重
- 解法二：排序 + 双指针
- - 处理细节问题
  - - 1、去重
    - - 越界问题
    - 2、不漏
五、编写代码
六、时间复杂度和空间复杂度

一、题目链接

三数之和

二、题目

在这里插入图片描述

三、题目解析

i != j 且 j != k 且 i != k表示三元组的下标不同。

题干中的注意要结合示例1理解：不可以包含重复的三元组，表示若多个三元组中的元素一样但顺序不一样，那这些就是重复的三元组，就只保留1种情况即可。

示例1中的注意：输出的顺序和三元组的顺序并不重要，表示返回的三元组中的数据顺序无所谓以及几组三元组的返回结果的返回顺序也不重要。

像示例2这种可能没有返回结果，那就返回空集；像示例3只有一组结果直接返回即可。

四、算法原理

其实本题难点在处理细节问题操作，待会会讲解。

最先想到的一定是暴力解法，因为最优解都是在暴力解法的基础上优化的。

解法一：排序 + 暴力枚举 + 利用set去重

之前做过两个数之和，同理，这里先枚举出所有的三元组，再去重，最后求和看是否等于0。

每枚举出一个三元组，就对这个三元组排序，若多个三元组排序结果相同，那就只保留一个即可。但是每一个三元组都要排序一遍就很繁琐，所以可以先对数组排好序，再从左向右暴力枚举（分别固定三个数，也就是三个for循环嵌套，时间复杂度是O(n^3)）。提前排好序就省去了每找到一个三元组就要排序的操作：

在这里插入图片描述

关于去重操作：可以利用容器unordered_set去重，把多个数组放入其中，最终在容器中的就是去重后的结果，从容器中拿出来即可。因为去重操作是容器解决的，并且每一个三元组只有有限的3个数，所以去重操作的时间复杂度是个常数级别的，可以忽略不计。

解法二：排序 + 双指针

该解法是在暴力解法的基础上优化的。

数组有序后，看到有序数组就要想到两种算法：二分和双指针。若能用双指针就不要用二分，因为用双指针能把时间复杂度降掉一维，例如，O(n^2)会降到O(n)、O(n)会降到O(1)，是个非常优秀的算法。

和为s的两个数中利用双指针算法解决两个数的和等于目标值。同理，三数之和也可以用双指针接解决。

步骤：

排序。
从左向右依次固定一个数a。当a为正数时，不能在后面找到和为负数的两个数。所以固定数a区间就是a <= 0。
在固定数后面的区间内，利用"双指针算法"找到所有两数之和等于-a的二元组。

在这里插入图片描述

处理细节问题

1、去重

面试题：不利用容器set，想个更优秀的去重解法。

两个地方需要去重：

找到一种结果之后，left和right指针要跳过重复元素。
当使用完一次"双指针算法"后，i也需要跳过重复的元素。

数组已有序，说明重复的三元组结果放到了一起。例如下面示例，找到目标二元组[ 0，4 ]，left和right就要分别跳过当前所指元素的所有重复元素：

为什么有3个0的情况下，最后一个元素3也要跳过呢？因为固定数、目标值以及元素0确定的话，那么另一个满足的元素只有4了，而这个三元组是重复的三元组，需要去重。所以，一旦找到目标三元组，left和right就要跳过重复的元素。

在这里插入图片描述
还是上图的示例，当把第一个-4枚举完，要枚举第二个-4时，问题来了：之前已经固定过-4，那么再固定-4又会出现与之前相同的二元组，i直接跳到元素-1找二元组。所以，当使用完一次"双指针算法"后，i也需要跳过重复的元素。

越界问题

去重可能会越界，left、right、i 移动会有越界访问的情况，例如：

在这里插入图片描述

2、不漏

找到所有与目标值一样的二元组（“所有”：保证不漏）。

当left和right所指相加等于目标值，直接left++（中间一坨数分别与left相加都 <= target）、right–（中间一坨数分别与right相加都 >= target），并且left和right都要跳过重复的元素，缩小区间，继续找二元组，保证不漏。

五、编写代码

大括号会形成vector< int >的数组，push_back到ret里：

vector<vector<int>> ret;
ret.push_back({ nums[i], nums[left], nums[right] });

小优化：

if (nums[i] > 0) break;

避免i、left、right越界：

在这里插入图片描述

去重i中的while循环中的++i会与for循环的++i重复++，所以可以把for循环的第三个语句置为空，i移动的操作放到循环里面完成。for循环的三个语句都可以为空：

在这里插入图片描述

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 1.排序sort(nums.begin(), nums.end());// 2.依次固定一个数a，在该数右区间内用双指针算法找和为-a的所有二元组int n = nums.size();for (int i = 0; i < n; ){if (nums[i] > 0) break;int left = i + 1, right = n - 1, target = -nums[i];while (left < right){int sum = nums[left] + nums[right];if (sum > target) --right;else if (sum < target) ++left;else {// 找到一种结果，继续找，不要漏ret.push_back({ nums[i], nums[left], nums[right] });++left, --right;// 去重 left和rightwhile (left < right && nums[left] == nums[left - 1]) ++left;while (left < right && nums[right] == nums[right + 1]) --right;}}// 每使用完一次双指针，去重i++i;while (i < n && nums[i] == nums[i - 1]) ++i;}return ret;}
};

六、时间复杂度和空间复杂度

for循环套while循环，这个while循环执行的次数是n次，同理，去重i操作也有可能是执行n次，因此时间复杂度是O(n^2)。

排序会占logn的压栈空间，空间复杂度是O(logn)。

三数之和

一、题目链接

二、题目

三、题目解析

四、算法原理

解法一：排序 + 暴力枚举 + 利用set去重

解法二：排序 + 双指针

处理细节问题

1、去重

越界问题

2、不漏

五、编写代码

六、时间复杂度和空间复杂度

相关文章：