学步园

一、     题目

给出一个数组S包含n个整数，找出不重复的三个元素a、b、c使a+b+c=0。

例如给出S = {-10 1 2 -1 -4},

结果是:

    (-1, 0, 1)

    (-1, -1, 2)

二、     分析

首先我们看到这个题目会想到Brute-Force(简单的模式匹配)直接使用三重循环来匹配所有元素组合找出结果。虽然我在每一层循环都做了优化来减少一些遍历，但是仍然不能在数量级上减少，所以总是超时。

Brute-Force(简单的模式匹配)超时代码：

//超时 
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
    	int len = num.size();
    	int res;
    	vector<vector<int>> ans;
    	if(len<=2) return ans;
        for(int i=0;i<len-2;i++){
        	for(int j=i+1;j<len-1;j++){
        		res = 0-num[i]-num[j];
        		for(int k=j+1;j<len;j++){
        			if(num[k] == res){
        				vector<int> ves;
        				ves.push_back(num[i]);
        				ves.push_back(num[j]);
        				ves.push_back(num[k]);
        				ans.push_back(ves);
        			}	
        		}
        	}
        }
        return ans;
    }
};

所以我们要换个思路，一般情况下对于数组的查询我们为了方便总是希望它是有序的，因此第一步应该要将数组排序，那么接下来我们就将当前的节点作为第一个元素，那么接下来就是寻找剩下的两个元素，因为它已经是有序的了，所以可以使用左右指针法，设置左右指针夹逼，总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n)

但注意为了避免重复，对于排序后的数组，当我们枚举第一个数时，如果遇到重复的就直接跳过，这一点其实很重要，我没有写的时候一会超时；还有一点当我们找到一个符合的二元组（第二个数和第三个数）时，也分别对第二个数和第三个数去重。可以看出这道题细节处理是否到位决定了能否通过。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
    	int len = num.size();
    	//中间结果、左指针、右指针 
    	int res,left,right;
    	vector<vector<int>> ans;
    	if(len<=2) return ans;
    	//将数组排序 
    	sort(num.begin(), num.end());
        for(int i=0;i<len-2;i++){
        	//将重复的忽略，ps：刚开始没有关心这一点,总是超时，加上后秒过，汗... 
        	while(i > 0 && i < len - 2 && num[i] == num[i - 1])
                ++i;
        	res = -num[i];
        	left = i+1;
        	right = len -1;
        	while(left<right){
        		//寻找符合元素 
        		if(num[left] + num[right] < res){
        			left++;
        		}
        		else if(num[left] + num[right] > res){
        			right--;
        		} 
        		else {
        			//将结果放入ans 
        			vector<int> ves;
        			ves.push_back(num[i]);
        			ves.push_back(num[left]);
        			ves.push_back(num[right]);
        			ans.push_back(ves);
        			//解决重复问题 
        			left++;
					while(left < right && num[left] == num[left-1])
						left++;
					right--;
					while(left < right && num[right] == num[right+1])
						right--;		
        		}
        	}
        }
        return ans;
    }
};