http://oj.leetcode.com/problems/3sum/
找出三个数的和是0的元组.
class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > ans; if(num.size()<3) return ans; sort(num.begin(),num.end()); // 排序处理 for(int i = 0;i<num.size()-2;i++) { for(int j = i+1;j<num.size()-1;j++) { if(num[i] + num[j] >0) break; if(num[i]+num[j]+num[num.size()-1]<0) continue; for(int k = j+1;k<num.size();k++) { if(num[i]+num[j]+num[k]==0) { vector<int> onePiece; onePiece.push_back(num[i]); onePiece.push_back(num[j]); onePiece.push_back(num[k]); int flag = 0; for(int t = 0;t<ans.size();t++) { if(num[i] == ans[t][0] && num[j]== ans[t][1] && num[k] == ans[t][2]) { flag = 1; break; } } if(flag == 0) ans.push_back(onePiece); break; } if(num[i]+num[j]+num[k]>0) break; } } } return ans; } };
尽管加上了各种剪枝，还是超时，于是参考了别人的代码。
vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > ans; if(num.size()<3) return ans; sort(num.begin(),num.end()); // 排序处理 vector<int> onePiece; for(int i = 0;i<num.size()-2;i++) { int j = i+1; int k = num.size()-1; while(j<k) { if(num[i]+num[j]+num[k]>0) k--; else if(num[i]+num[j]+num[k]<0) j++; else { onePiece.clear(); onePiece.push_back(num[i]); onePiece.push_back(num[j]); onePiece.push_back(num[k]); ans.push_back( onePiece); j++; k--; } } } ans.erase(unique(ans.begin(),ans.end()),ans.end()); return ans; }
这样固定 i 之后，同时调整 j k 在思路上清晰，效果也确实好，复杂度为 O(n2).
但是运行结果为 Output Limit Exceeded
原文：http://www.cnblogs.com/qingcheng/p/3547942.html