class Solution { public: //求三数之和,从两数之和而来,一个循环固定一个数,循环内进行双指针:相当于求两数之和为第三数的相反值 //考虑重复问题,同样,未使用或者正在使用是可以使用本数的,而相同的数使用过了,这个数就不能使用了,标记且跳过; vector<vector<int> > threeSum(vector<int>& num) { if(num.size() < 3)return {}; //不能成组时,直接返回,不然在指针赋值时,超出数组 vector< vector<int> > ans = {}; sort(num.begin(), num.end()); vector<int> visit( num.size() , 0); //其实可以不用标记,在重复时,直接跳过即可 for(int i=0; i<num.size()-2; i++){ if(i>0 && num[i] == num[i-1] && visit[i-1] == 2){ visit[i] = 2; continue; } visit[i] = 1; int left = i+1; int right = num.size()-1; while(left < right){ if( num[left]==num[left-1] && visit[left-1]==2 ){ visit[left] = 2; left++; continue; } if( right < num.size()-1 && num[right]==num[right+1] && visit[right+1] ==2 ){ visit[right] = 2; right--; continue; } if(num[left] + num[right] == -num[i]){ ans.push_back({num[i], num[left], num[right]}); visit[left] = 2; visit[right] = 2; left++; right--; //移动指针 }else if( num[left] + num[right] < -num[i] ){ left++; }else if( num[left] + num[right] > -num[i] ){ right--; } } std::fill(visit.begin()+i+1, visit.end(), 0); //清空记录 visit[i] = 2; } return ans; } };