Description

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源：leetcode.com 15 3Sum

Solution

Approach 1

这道题有点难度，第一时间没有什么思路。我想到的主要问题是如何保证返回结果中不包含重复的一组数。如果使用暴力解法，将所有满足条件的组合取到后进行重复性清洗，应该是一种可行的解法，只是这样做时间复杂度有点高。

下面的代码就是暴力解法的实现。不出意外，在leetcode中结果为超时。这种算法的时间复杂度为 O(n^3 * nlogn) + O(n^2) 。

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    for (size_t i=0; i<nums.size(); ++i) {
	int n1 = nums[i];
	for (size_t j=i+1; j<nums.size(); ++j) {
	    int n2 = nums[j];
	    for (size_t k=j+1; k<nums.size(); ++k) {
		int n3 = nums[k];
		if (n1 + n2 + n3 == 0) {
		    vector<int> triplet{n1, n2, n3};
		    sort(triplet.begin(), triplet.end());
		    ans.push_back(triplet);
		}
	    }
	}
    }

    // 将结果中的重复组合删掉
    for (vector<vector<int>>::iterator it1 = ans.begin();
	 it1 != ans.end(); ++it1) {
	for (vector<vector<int>>::iterator it2=it1+1; it2!=ans.end();) {
	    if (*it1 == *it2) {
		it2 = ans.erase(it2);
	    }
	    else {
		++it2;
	    }
	}
    }

    return ans;
}

从上面这个解法中，我能够得到的 教训 经验是对 vector 进行具有删除操作的循环时，使用迭代器完成更不容易出错。我之前的去重逻辑是这样的。

for (int i=0; i<ans.size(); ++i) {
    for (int j=i+1; j<ans.size(); ++j) {
	if (ans[i] == ans[j]) {
	    ans.erase(ans.begin() + j);
	}
    }
}

很显然，上面的代码在一些情况下并不能彻底删去所有重复的元素，下面的代码才是真正正确的实现。

for (int i=0; i<ans.size(); ++i) {
    for (int j=i+1; j<ans.size();) {
	if (ans[i] == ans[j]) {
	    ans.erase(ans.begin() + j);
	}
	else {
	    ++j;
	}
    }
}

Approach 2

我认为这到题的主要难点啊主要是在去除重复的问题上。下面的解法来自 leetcode ，在处理重复性问题时，在匹配答案时将重复的数字跳过，这样就不用在后续的结果中进行剔除重复元素的步骤了。

vector<vector<int> > threeSum(vector<int> &num) {

    std::sort(num.begin(), num.end());

    vector<vector<int> > res;
    for (int i = 0; i < num.size(); i++) {

	int target = -num[i];
	int front = i + 1;
	int back = num.size() - 1;

	while (front < back) {

	    int sum = num[front] + num[back];

	    // Finding answer which start from number num[i]
	    if (sum < target)
		front++;

	    else if (sum > target)
		back--;

	    else {
		vector<int> triplet = {num[i], num[front], num[back]};
		res.push_back(triplet);

		// Processing duplicates of Number 2
		// Rolling the front pointer to the next different number forwards
		while (front < back && num[front] == triplet[1])
		    ++front;
	    }
	}

	// Processing duplicates of Number 1
	while (i + 1 < num.size() && num[i + 1] == num[i])
	    ++i;
    }

    return res;
}

上面的代码中，只需要跳过 front 所对应的数字就好，因为 back 对应的数字会自然地随 front 变化而变化。