LeetCode 刷题【15. 三数之和】

15. 三数之和

自己做

解1：三层for循环（超时）

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int len = nums.size();vector<vector<int>> res;for (int i = 0; i < len; i++)for (int j = i + 1; j < len; j++)for (int k = j + 1; k < len; k++)if (i != j && i != k && j != k && (nums[i] + nums[j] + nums[k] == 0)) {int res_len = res.size();if (res_len > 0) {bool unique = true; //标记是否唯一for (int r = 0; r < res_len; r++)                       //检查是否重复if (res[r][0] == nums[i] && res[r][1] == nums[j] && res[r][2] == nums[k] ||          //重复res[r][0] == nums[i] && res[r][1] == nums[k] && res[r][2] == nums[j] ||res[r][0] == nums[j] && res[r][1] == nums[k] && res[r][2] == nums[i] ||res[r][0] == nums[j] && res[r][1] == nums[i] && res[r][2] == nums[k] ||res[r][0] == nums[k] && res[r][1] == nums[i] && res[r][2] == nums[j] ||res[r][0] == nums[k] && res[r][1] == nums[j] && res[r][2] == nums[i])unique = false; //如果有重复则标记为falseif(unique)          //无重复res.push_back(vector<int>({ nums[i] , nums[j] , nums[k] }));}else {                                                        //首个三元组不考虑res.push_back(vector<int>({ nums[i] , nums[j] , nums[k] }));}}return res;}
};

解2：两层for+哈希（超时）

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int len = nums.size();map<int, int> m;vector<vector<int>> res;for (int i = 0; i < len; i++)m.insert(make_pair(nums[i], i));for (int i = 0; i < len; i++)for (int j = i + 1; j < len; j++) {map<int,int>::iterator num3 = m.find(-(nums[i] + nums[j]));if (num3 != m.end()) {                 //找到相匹配的的num3 => num1 + num2 = - num3int k = num3->second;//检查是否存在重复if (i != k && j != k) {int res_len = res.size();if (res_len > 0) {bool unique = true; //标记是否唯一for (int r = 0; r < res_len; r++)                       //检查是否重复if (res[r][0] == nums[i] && res[r][1] == nums[j] && res[r][2] == nums[k] ||          //重复res[r][0] == nums[i] && res[r][1] == nums[k] && res[r][2] == nums[j] ||res[r][0] == nums[j] && res[r][1] == nums[k] && res[r][2] == nums[i] ||res[r][0] == nums[j] && res[r][1] == nums[i] && res[r][2] == nums[k] ||res[r][0] == nums[k] && res[r][1] == nums[i] && res[r][2] == nums[j] ||res[r][0] == nums[k] && res[r][1] == nums[j] && res[r][2] == nums[i])unique = false; //如果有重复则标记为falseif (unique)          //无重复res.push_back(vector<int>({ nums[i] , nums[j] , nums[k] }));}else {                                                        //首个三元组不考虑res.push_back(vector<int>({ nums[i] , nums[j] , nums[k] }));}}}}return res;}
};

 

看题解

 双指针化两层for循环为一层

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int len = nums.size();vector<vector<int>> res;//排序数组sort(nums.begin(), nums.end());for (int first = 0; first < len; first++) {int third = len - 1;                                    //右指针【指向最大值】while (first < len && first > 0 && nums[first] == nums[first - 1]) {            //上一回相等的情况下，为防止撞车，所以first不能等于原来的值first++;}for (int second = first + 1; second < third; second++) {while (second < third && second > first + 1 && nums[second] == nums[second - 1]) {            //上一回相等的情况下，为防止撞车，所以second不能等于原来的值second++;}while(second < third && !(nums[first] + nums[second] + nums[third] == 0)){if (second < third && nums[first] + nums[second] + nums[third] > 0) {                      //右指针third大了third--;}if (second < third && nums[first] + nums[second] + nums[third] < 0) {                      //左指针second小了second++;}}//找到nums[first] + nums[second] + nums[third] = 0，将结果存放if (second < third && nums[first] + nums[second] + nums[third] == 0)res.push_back(vector<int>({ nums[first], nums[second], nums[third] }));}}return res;}
};