c++ 3sum 109ms


  • 0
    Y

    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;

    	if (nums.size() < 3) return result;
    	sort(nums.begin(), nums.end());
    
    	for (int i = 0; nums[i] <= 0 && i < nums.size() - 2; i++)
    	{
    		if (nums[i] == 0 )
    		{
    			if (i + 2 < nums.size() && nums[i + 1] == 0 && nums[i + 2] == 0)
    			{
    				vector<int> empty;
    				empty.push_back(0); empty.push_back(0); empty.push_back(0);
    				result.push_back(empty);
    				return result;
    			}
    			else
    			{
    				return result;
    			}
    		}
    
    		int front = i + 1;
    		int back = nums.size() - 1;
    		while (front < back)
    		{
    			int sum = nums[front] + nums[back];
    			if (sum < -nums[i])
    			{
    				front++;
    			}
    			else if (sum > -nums[i])
    			{
    				back--;
    			}
    			else
    			{
    				vector<int> resultkid;
    				resultkid.push_back(nums[i]);
    				resultkid.push_back(nums[front]);
    				resultkid.push_back(nums[back]);
    				result.push_back(resultkid);
    				front++;
    				back--;
    				while (front < back && nums[front] == resultkid[1]) front++;
    				while (front < back && nums[back] == resultkid[1]) back--;
    			}
    		}
    		while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;
    	}
    	return result;
    }

Log in to reply
 

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