[LeetCode]3Sum

这道题可以reduce成2sum的问题，我们遍历[0, N)的元素，每次锁定第一个元素，之后右边的subarray就会变成two sum问题。2sum有两种解法，写代码的时候要注意去重。

HashMap解法:
主要是去重的部分，sort输入array。如果第一个元素之前visit过了，我们直接跳过。对于2sum的部分，我们不能简单的check上一个元素是不是和当前元素相同然后跳过，这样的话我们会漏掉一些情况，比如输入为(0, 0, 0)我们就找不到和为0的一对pair。所以我们需要把去重的部分放在找到符合条件的pair的时候，一旦找到了我们就跳过之后所有重复的元素。时间复杂度为O(N^2)，空间O(N)。代码如下：

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	int len = nums.size();
	sort(nums.begin(), nums.end());
	vector<vector<int>> res;
	for(int i = 0; i < len; ++i)
	{
	if(i && nums[i] == nums[i - 1])continue;
	//from here it is 2 sum problem
	unordered_set<int> visited;
	for(int j = i + 1; j < len; ++j)
	{
	//don't check duplicates here and skip
	int sum = nums[i] + nums[j];
	if(visited.find(-sum) != visited.end())
	{
	res.push_back({nums[i], -sum, nums[j]});
	//remove duplicates, only need to skip after we added a result contains this number
	//otherwise it will be wrong in case (0, 0, 0)
	while(j + 1 < len && nums[j] == nums[j + 1])++j;
	}
	visited.insert(nums[j]);
	}
	}
	return res;
	}
	};

view raw 3Sum.cpp hosted with ❤ by GitHub

Two pointer解法：
同样要sort，和HashMap的去重方法是类似的，一旦我们找打了和为target的一对pair，两个指针一直移动跳过所有的重复元素。时间复杂度为O(N^2)，常数空间。代码如下:

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	int len = nums.size();
	sort(nums.begin(), nums.end());
	vector<vector<int>> res;
	for(int i = 0; i + 2 < len; ++i)
	{
	if(i && nums[i] == nums[i - 1])continue;
	int j = i + 1, k = len - 1;
	while(j < k)
	{
	int sum = nums[i] + nums[j] + nums[k];
	if(sum > 0)--k;
	else if(sum < 0)++j;
	else
	{
	res.push_back({nums[i], nums[j++], nums[k--]});
	//remove duplicates
	while(j < k && nums[j] == nums[j - 1])++j;
	while(j < k && nums[k] == nums[k + 1])--k;
	}
	}
	}
	return res;
	}
	};

view raw 3Sum_2.cpp hosted with ❤ by GitHub