Using two sum code and avoiding duplicates to get O(N^2) solution


  • 0
    G
    vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int> > ans;
            if(nums.size()<3) return ans;
            sort(nums.begin(),nums.end());
            int i,j,k,sum;
            vector<int> temp(3);
            for(i=0;i<nums.size()-2;i++)
            {
                if(i>0 && nums[i-1]==nums[i]) continue;//To avoid duplicates through first value
                j=i+1,k=nums.size()-1;
                while(j<k)
                {
                    sum = nums[i]+nums[j]+nums[k];
                    if(sum>0)  k--;
                    else if(sum<0)j++;
                    else 
                    {
                        temp[0]=nums[i],temp[1]=nums[j],temp[2]=nums[k];
                        ans.push_back(temp),k--,j++;
                        while(k>j && nums[j]==nums[j-1])j++;//To avoid duplicates through second value
                        while(k>j && nums[k]==nums[k+1])k--;//To avoid duplicates through third value
                    }
                }
            }
            return ans;

Log in to reply
 

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