My own C++ solution,beat 88%


  • 0
    W
    class Solution {
    public:
    	vector< vector<int> > threeSum(vector<int>& nums) {
    		vector< vector<int> > ret;
    		sort(nums.begin(), nums.end());
    		int zeroIndex = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();
    		vector<int> left(nums.begin(), nums.begin() + zeroIndex);
    		vector<int> right(nums.begin() + zeroIndex, nums.end());
    		if (right.size() >= 3 && right[0] ==0 && right[1] ==0 && right[2] == 0) {
    			vector<int> tmp(3, 0);
    			ret.push_back(tmp);
    		}
    		//left go first
    		for (int i = 0; i < left.size(); i++) {
    			if (i != 0 && left[i] == left[i - 1]) continue;
    			int index = upper_bound(right.begin(), right.end(), -left[i]) - right.begin() - 1;
    			int j = 0;
    			while (j < index) {
    				if ((right[j] + right[index]) == -left[i]) {
    					vector<int> tmp;
    					tmp.push_back(left[i]);
    					tmp.push_back(right[j]);
    					tmp.push_back(right[index]);
    					ret.push_back(tmp);
    					j++;
    					index--;
    					while(right[j]==right[j-1]) j++;
    					while(right[index]==right[index+1]) index--;
    				}
    				else if ((right[j] + right[index]) > -left[i]) {
    					index--;
    				}
    				else if ((right[j] + right[index]) < -left[i]) {
    					j++;
    				}
    			}
    		}
    
    		//right go second
    		for (int i = 0; i < right.size(); i++) {
    			if (i != 0 && right[i] == right[i - 1]) continue;
    			int index = upper_bound(left.begin(), left.end(), -right[i]) - left.begin();
    			int j = left.size() - 1;
    			while (index < j) {
    				if ((left[j] + left[index]) == -right[i]) {
    					vector<int> tmp;
    					tmp.push_back(right[i]);
    					tmp.push_back(left[j]);
    					tmp.push_back(left[index]);
    					ret.push_back(tmp);
    					j--;
    					index++;
    					while(left[j]==left[j+1]) j--;
    					while(left[index-1]==left[index]) index++;					
    				}
    				else if ((left[j] + left[index]) < -right[i]) {
    					index++;
    				}
    				else if ((left[j] + left[index]) > -right[i]) {
    					j--;
    				}
    			}
    		}
    
    		return ret;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.