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

专题一_双指针_三数之和

news 2025/7/10 14:05:16

一：题目解析

题目链接：15. 三数之和 - 力扣（LeetCode）

注：懂下面这道题再看三数之和会简单很多：专题一_双指针_查找总价格为目标值的两个商品-CSDN博客

解析：

1：要找不同位置的三元组，也就是不能同一个元素重复使用

2：三元组重复的定义：假设找到了[-1,0,1] 和 [0,1,-1]，尽管不是三个位置的值顺序不同，但是只要是三元组的值相同则为重复！

3：输出的三元组的顺序不重要，可以[-1,0,1]，也可以变成 [0,1,-1]

二：算法原理

①：暴力

暴力枚举出来符合要求的三元组，我们还需要去重，所以可以选择对每个三元组进行排序，让其组内是升序，再利用unordered_set<vector<int,int,int>>进行去重，但太过于麻烦

所以可以先对数组进行排升序，再暴力，最后符合要求的三元组直接进行unordered_set去重，但仍然不优秀，时间复杂度高达N^3 (找三元组的三重循环就为N^3)

②：优秀

根据上一题：专题一_双指针_查找总价格为目标值的两个商品-CSDN博客的思路，所以此题无非就是固定最左面的数，其值为targe，然后再剩余的区间找和为-targe的两个值，三元组的和为0！

所以思路：

1：仍然是对初始数组进行排序

2：固定最左面的数，其值为targe

3：该targe往右的区间内，进行双指针找到两个数的和为-targe即可

例子：[-4,-4,-1,0,0,0 1,1,4,4,5,6] ，固定targe为最左的-4，然后在右面的区间找和为4的两个数

4：去重

去重，按照暴力解法采取unordered_set可以，但是不优秀，哈希的开辟和插入都需要耗费时间复杂度，所以我们不用容器，我们可以自己进行去重，虽然理解更难，但是算法更优秀

对双指针的去重：

比如：[-4,-4,-1,0,0,0 1,1,4,4,5,6]中，此时当我们进行到了left为第一个0，right为最后一个4的时候此时我们找到了和为-4的两个值，然后组成三元组[-4,0,4]，然后此时肯定是要left++，right--的，但是呢！left后面的值和组成三元组的0是重复的，right前面的值和组成三元组的4是重复的，所以我们可以直接left移动到1，right也移动到1，再做下次的判断，如图：

但是left如果后面的值都是0，则有可能在去重的时候越界了，right同理！所以我们还要加一步判断，就是在left<right的前提才进行去重！

对targe的去重：

当targe身为第一个-4的情况遍历完了之后，targe也没有必要再移动到下一个-4了，而是移动到下一个不是-4的位置，同样的，如果全是-4，则targe在去重过程中也会越界，应该加一个targe的小标<n(元素个数)的判断！

一个小优化：

当targe值>0的时候，此时没有必要进行双指针查找三元组的必要了，因为数组本来一开始就是升序，你targe值>0了，再加上后面的两个值，肯定不可能为0！！

三：代码编写

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> v;//返回值int n = nums.size();//n的定义 sort(nums.begin(), nums.end());//对数组先进行排序 形成升序for (int i = 0; i < n;) {//targe值的固定(从左到右)if (nums[i] > 0) break;//一个小优化 int left = i + 1, right = n - 1, targe = nums[i];//根据i下标 确认left的位置 right初始为最右 targe为固定位置的值while (left < right) {//两指针相遇 代表此次的targe值已经无效 int sum = nums[left] + nums[right];//双指针的和为sumif (sum < -targe) left++;//和小于-targe 代表left应该++else if (sum> -targe) right--;//和大于-targe 代表right应该--else {//代表sum = -targe 找到三元组了v.push_back({nums[i], nums[left], nums[right]});//把这个三元组放进返回值v中left++,right--;//双指针移动while (left < right && nums[left] == nums[left - 1]) //left指针的去重left++;while (left < right && nums[right] == nums[right + 1]) //right指针的去重right--;}}i++;//i移动 也就是targe值的改变while (i < n && nums[i] == nums[i - 1]) i++;//targe值的去重}return v;//返回v}
};

解释：

1：targe为固定的值，所以双指针的和sum和-targe进行比较

2：left right targe的去重，先++(本来就要++)，再判断如果相等，就再++，知道和上一次不相等

3：targe的去重，本质就是i的移动，我们在下面已经让targe成为了应该成为的值，所以就去掉了for循环中的i++，否则会出错！如图：