LeetCode 15. 3Sum

LeetCode 15. 3Sum

Description:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

---

分析：

首先，判断数组长度，若小于3，直接返回空二维vector；
将数组按从小到大排序，先确定nums[i]为第一个元素，为了避免重复，如果nums[i]和nums[i-1]相等就continue，然后设定两个变量begin和end，begin指向i+1，end指向n-1；
判断此时sum是否等于0，如果等于0就将结果放入result数组中，且begin++，end--，为了避免重复，如果begin++后的元素依旧和刚才的元素相等，继续begin++，end同理
如果sum大于0，则end--；若果sum小于0，就将begin++；
最后返回result二维数组。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	vector<vector<int> > threeSum(vector<int>& nums) {
		vector<vector<int> > result;
		int n = nums.size();
		if (n < 3) return result;
		sort(nums.begin(), nums.end());
		vector<int> temp(3);
		for (int i = 0; i < n; i++) {
			if (nums[i] > 0) break;
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			int begin = i + 1, end = n - 1;
			while (begin < end) {
				int sum = nums[i] + nums[begin] + nums[end];
				if (sum == 0) {
					temp[0] = nums[i];
					temp[1] = nums[begin];
					temp[2] = nums[end];
					result.push_back(temp);
					begin++;
					end--;
					while (begin < end && nums[begin] == nums[begin - 1]) begin++;
					while (begin < end && nums[end] == nums[end + 1]) end--;
				}
				else if (sum > 0) {
					end--;
				}
				else {
					begin++;
				}
			}
		}
		return result;
	}
};
int main() {
	int n;
	cin >> n;
	vector<int> nums;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		nums.push_back(t);
	}
	Solution s;
	vector<vector<int> > result = s.threeSum(nums);
	for (int i = 0; i < result.size(); i++) {
		for (int j = 0; j < result[i].size(); j++) {
			cout << result[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}