Leetcode: 3Sum

3Sum.cpp

class Solution {
public:
	vector<vector<int> > threeSum(vector<int> &num) {
		sort(num.begin(), num.end());
		vector<vector<int> > ans;

		int N = num.size();
		int pre = INT_MIN;
		for (int i = 0; i < N; ++i) {
			if (num[i] == pre) continue;
			pre = num[i];

			int x = 0-num[i];
			int l = i+1;  int r = N-1;
			while (l<r) {
				if (num[l] + num[r] < x) ++l;
				else if (num[l] + num[r] > x) --r;
				else {
					vector<int> vec;  vec.push_back(num[i]);
					vec.push_back(num[l]);  vec.push_back(num[r]);
					ans.push_back(vec);
					++l;
					while (l<=r && num[l]==num[l-1]) ++l;
				}
			}
		}
		return ans;
	}
};
class Solution {
public:
	struct Rec {
		vector<int> num;
		Rec(const vector<int> &_num) : num(_num) {}
		bool operator==(const Rec & rec) const {
			return num[0]==rec.num[0] && num[1]==rec.num[1] && num[2]==rec.num[2];
		}
		bool operator<(const Rec & rec) const {
			for (int i = 0; i < 3; ++i) {
				if (num[i] < rec.num[i]) return true;
				else if (num[i] > rec.num[i]) return false;
			}
			return false;
		}
	};
	vector<vector<int> > threeSum(vector<int> &num) {
		set<Rec> st;
		vector<vector<int> > ans;

		sort(num.begin(), num.end());
		int N = num.size();
		int pre = INT_MIN;
		for (int i = 0; i < N; ++i) {
			if (num[i] == pre) continue;
			pre = num[i];

			int x = 0-num[i];
			int l = 0;  int r = N-1;
			while (l<r) {
				if (num[l] + num[r] < x) ++l;
				else if (num[l] + num[r] > x) --r;
				else {
				    if (l != i && r!= i) {
					    vector<int> vec;  vec.push_back(num[i]);
		    			vec.push_back(num[l]);  vec.push_back(num[r]);
		    			sort(vec.begin(), vec.end());
		    			st.insert(Rec(vec));
					}
					++l;
				}
			}
		}
		for (set<Rec>::iterator it = st.begin(); it != st.end(); ++it)
			ans.push_back(it->num);
		return ans;
	}
};

@zrqsmcx 我跟你解法一样，
29行这里 可以改成下面的样子，复杂度上没什么提高，但是就不用判断 if (l != i && r!= i) 了

int l = i+1;  int r = N-1;  // int l = 0;  int r = N-1;

int l = i+1; int r = N-1;
聪明！科学！对于l < i的情况，必然是之前已经处理过的，给力！

是很不错的优化啊！减少了很多重复！

792ms => 420ms

@eclipselu
我根据你的思路改了一下，现在上面的是好的版本，在30行以内，276ms。
我之前做了好多废操作啊！

@zrqsmcx 嗯 互相review一下吧 你也看看我的有什么可以优化的地方