首页 > 代码库 > [LeetCode]3 Sum
[LeetCode]3 Sum
思路: 1.将数组排序，
2.a 遍历 数组a[0]....a[n-1];
3.当 a=a[i] 时 后面的问题 就是 : a[i+1] 到 a[n-1]中 b+c =-a （编程之美 2.12 快速寻找满足条件的两个数 ）
记 b=a[j]=a[i-1] c=a[k]=a[n-1]
若 b+c < -a ，j++;
b+c > -a ，j--;
b+c=-a 记录下来，并j++;
4.还有一个问题 就是unique triplet, 所以 a=a[i] 要判断是否和a[i-1]相等，若相等，子问题已经解答。
也要判断 b和c 是否和之前的相同，若相同，就已经判断过了。
// 3Sum.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <vector>#include <algorithm>#include <iostream>using namespace std;bool myComp(int x1, int x2){ return x1 < x2;}class Solution {public: vector<vector<int> > threeSum(vector<int> &num) { sort(num.begin(), num.end(), myComp); int p1 = 0, p2 = 0; vector<vector<int> > res; if (num.size() < 3) return res; for (int i = 0; i < num.size()-2; i++) { if (i>0 && num[i] == num[i - 1])continue; int sum = -num[i]; p1 = i + 1; p2 = num.size() - 1; while (p1<p2) { //while (p1!=1&&num[p1] == num[p1 -1])p1++; while ((p1!=i+1)&&num[p1] == num[p1-1])p1++; while ((p2!=num.size()-1)&&(p2>0)&&(num[p2] == num[p2 +1]))p2--; if (p1 >= p2)break; //cout << "(" << i << "," << p1 << "," << p2 << ")" << endl; if (num[p1] + num[p2] == sum) { vector<int>tempV; tempV.push_back(num[i]); tempV.push_back(num[p1]); tempV.push_back(num[p2]); res.push_back(tempV); //cout << "**" << i << "," << p1 << "," << p2 << endl; p2--; } else if (num[p1] + num[p2] > sum) { p2--; } else if (num[p1] + num[p2] < sum) { p1++; } } } return res; }};int _tmain(int argc, _TCHAR* argv[]){ vector<int>test; /* test.push_back(-1); test.push_back(0); test.push_back(1); test.push_back(2); test.push_back(-1); test.push_back(-4); */ test.push_back(0); test.push_back(0); test.push_back(0); test.push_back(0); test.push_back(0); test.push_back(0); Solution ss; vector<vector<int> > res = ss.threeSum(test); //cout << res.size()<<endl; for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res[i].size(); j++) cout << res[i][j] << ","; cout << endl; } system("pause"); return 0;}
[LeetCode]3 Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。