48 ms C++ solution


  • 1
    L
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            
            int size = nums.size();
            vector<int> temp;
            vector< vector<int> > ret_v;
            
            if(size<3)
                return ret_v;
            
            int start_idx=0, end_idx=size-1, sum=0,temp_sum=0;
            sort(nums.begin(),nums.end());
            
            for(int i=0;i<=size-3;i++)
            {
                if(nums[i]>0)
                    break;
                    
                if((nums[i]==nums[i-1]) && (i>0) && (i<=size-3))
                    continue;
                    
                sum = -nums[i];
                start_idx = i+1;
                end_idx= size-1;
                
                while(start_idx<end_idx)
                {
                    temp_sum = nums[start_idx]+ nums[end_idx];
                    
                    if(temp_sum == sum)
                    {
                        temp.push_back(nums[i]);
                        temp.push_back(nums[start_idx]);
                        temp.push_back(nums[end_idx]);
                        ret_v.push_back(temp);
                        temp.clear();
                        start_idx++;
                        end_idx--;
                        while(nums[start_idx]==nums[start_idx-1])
                            start_idx++;
                        while(nums[end_idx]==nums[end_idx+1])
                            end_idx--;
                        
                    }
                    else if(temp_sum <sum)
                        start_idx++;
                    else
                        end_idx--;
                }
            }
            
            return ret_v;
        }
    };

  • 0
    C

    if the input is [0,0,0,0,0,0], will the subscript of the vector be out of range in the following statements?

    while(nums[start_idx]==nums[start_idx-1])
    start_idx++;
    while(nums[end_idx]==nums[end_idx+1])
    end_idx--;


  • 0
    Y

    upvote the only 48 ms solution! thanks for your "if(nums[i]>0) break"


Log in to reply
 

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