题解 | #三数之和#
三数之和
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型vector * @return int整型vector<vector<>> */ //三数之和:转化成——有序中的两数和 //a+b+c=0 (三数中一定要有负数,有正数) 看成a+b=-c //去重:首先 排序 然后 按住一个数,后面结果 就是 a+ b = -c 在有序中找和为s的 所有两元组(要去重)遍历下一个按住的数,要看和上一个是否相等,如果相等就 跳过(continue ): void quicksort(vector<int>& num, int begin, int end) { if (num.size() == 0 || begin > end) return ; int left = begin, right = end; int tmp = num[left]; while (left != right) { while (left < right && num[right] >= tmp) right--; num[left] = num[right]; while (left < right && num[left] <= tmp) left++; num[right] = num[left]; num[left] = tmp; if (left - 1 > begin) { quicksort(num, begin, left - 1); } if (left + 1 < end) { quicksort(num, left + 1, end); } } } void TwoSum(vector<int> array, int left, int right, int sum, vector<vector<int> >& res) { cout<<sum<<" "<<left<<" "<<right<<endl; while (left < right) { if ((array[left] + array[right]) > sum) right--; else if ((array[left] + array[right]) < sum) left++; else { res.push_back({-sum, array[left], array[right]}); right--; left++; while (array[left] == array[left - 1]) left++; while (array[right] == array[right + 1]) right--; } } } vector<vector<int> > threeSum(vector<int>& num) { // write code here if (num.size() < 3) return{}; quicksort(num, 0, num.size() - 1); for (int i = 0; i < num.size(); i++) { cout << num[i] << " " ; } cout<< endl; vector<vector<int> > res; for (int i = 0; i < num.size() - 2; i++) { while (i > 0 && num[i] == num[i - 1]) i++; if (i >= num.size() - 2) break; TwoSum(num, i + 1, num.size() - 1, -num[i], res); } return res; } };