題目：



暴力方法：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;std::unordered_set<std::string> uniqueValues;//保證結果唯一for(int i=0;i<nums.size();i++){//三個值暴力求解for(int j=0;j<nums.size();j++){for(int k=0;k<nums.size();k++){if(i!=j && i!=k && j!=k && nums[i]+nums[j]+nums[k]==0){vector<int> temp;temp.push_back(nums[i]);temp.push_back(nums[j]);temp.push_back(nums[k]);sort(temp.begin(),temp.end());//排序ostringstream oss;oss<<temp[0]<<temp[1]<<temp[2];std::string temposs=oss.str();//cout<<oss.str()<<endl;// for(const auto & elem:uniqueValues){//     cout<<"---"<<elem<<endl;// }if(uniqueValues.find(temposs)!=uniqueValues.end()){//結果去重//cout<<temposs<<endl;}else{uniqueValues.insert(temposs);res.push_back(temp);}}}}}return res;}
};

優化方法1：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;std::unordered_set<std::string> uniqueValues;//保證結果唯一std::unordered_map<std::string,vector<int>>uniqueKVs;for(int i=0;i<nums.size();i++){//優化下，選擇二個for(int j=i+1;j<nums.size();j++){vector<int> temp;temp.push_back(nums[i]);temp.push_back(nums[j]);temp.push_back(0-(nums[i]+nums[j]));sort(temp.begin(),temp.end());//排序ostringstream oss;oss<<i<<","<<j;uniqueKVs[oss.str()]=temp;}}for(const auto & elem :uniqueKVs){//查找符合條件的std::string k=elem.first;size_t pos=k.find(",");int i=std::stoi(k.substr(0,pos));int j=std::stoi(k.substr(pos+1,k.size()-pos-1));        vector<int> temp=elem.second;for(int k=0;k<nums.size();k++){if(i!=j && i!=k && j!=k && nums[i]+nums[j]+nums[k]==0){ostringstream oss;oss<<temp[0]<<temp[1]<<temp[2];std::string temposs=oss.str();cout<<oss.str()<<endl;if(uniqueValues.find(temposs)!=uniqueValues.end()){//結果去重//cout<<temposs<<endl;}else{uniqueValues.insert(temposs);res.push_back(temp);}}}}return res;}
};

優化方法2：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(),nums.end());//排序 方便 去重 和查找for(int i=0;i<nums.size();i++){//優化下，選擇二個if(i==0 || nums[i] != nums[i-1]){//去除 越界 和重復的值int k=nums.size()-1;//雙指針 左右 逼近  使得并行查找for(int j=i+1;j<nums.size();j++){if(j==i+1 || nums[j]!=nums[j-1]){//去除 越界 和重復的值while(j<k && nums[i]+nums[j]+nums[k]>0){k--;//并行查找合適的 k對應的值}if(j==k){break;// 左邊和右邊 通過雙指針都 查找了，不能再存在符合條件的了}if(nums[i]+nums[j]+nums[k]==0){//獲得符合條件的res.push_back({nums[i],nums[j],nums[k]});}}}}}return res;}
};