专题一_双指针_三数之和
一:题目解析
题目链接: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++,否则会出错!如图:
解释:targe为-4的轮次已经过了,应该到-1,但是for循环还有i++,导致跳过-1,来到0了,错误!
四:题目分析
1:和上道题两数之和的区别在于,我们不是找到了一个结果就返回,而是返回全部结果去重后的结果
2:先排序的好处,不仅体现在了时间复杂度,更是方便了我们的去重,因为相同的值都会挨在一起!所以我们才可以手动的去重!
3:时间复杂度为:O(N²)
(排序 O(N log N)
可忽略,即使加上也远胜N^3)