题解 | #三数之和#
三数之和
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711
1 解题思路
结果要求输出的每组三个数按顺序排列,因此先进行排序。
三数之和简化成两数之和问题的方法:依次拿出num[0]到num[num.size()-2],则它的负值就是两数之和问题的目标值(target)。
在有序数组中寻找和为target的两个数可以用双指针法,头指针从前到后遍历,尾指针二从后到前遍历,直到头指针和尾指针重合或头指针到尾指针后面表明有可能等于target的目标组合都被访问过了。
当指针指向数值和 < target,头指针向后移动;
当指针指向数值和 > target,尾指针向前移动;
当指针指向数值和 = target,将该组数值保存下来。
class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int>> res; if(num.size()<3) return res; //先排序 sort(num.begin(),num.end()); for(int i=0;i<num.size()-2;++i){ if(i && num[i]==num[i-1]) continue; int target = -num[i]; //两数之和问题的目标值 int f_point = i+1; //头指针 int r_point = num.size()-1; //尾指针 while(f_point<r_point){ if(num[f_point]+num[r_point]==target){ //"f_point++和r_point--"含义:找到一组解后,头尾指针还要继续移动,因为可能还有其他解 res.push_back({num[i],num[f_point++],num[r_point--]}); //如果数组中有多个值相同,当它第一次访问该值时已经判断过了,再次遇到直接跳过 while(num[f_point]==num[f_point-1]&&f_point<r_point) f_point++; while(num[r_point]==num[r_point+1&&f_point<r_point]) r_point--; }else if(num[f_point]+num[r_point]>target) r_point--; else f_point++; } } return res; } };