my solution with unordered_map


  • 0
    S
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ret;
            if(nums.size()<=2)  return ret;
            sort(nums.begin(),nums.end());
            unordered_map<int,int> imap;
            for(int i=0,N = nums.size();i<=N-2;i++)
            {
                if(nums[i] + nums[i+1] + nums[i+2] > 0) break;
                if(i>0 && nums[i]==nums[i-1] || nums[i]+ nums[N-1] + nums[N-2]< 0 ) continue;
                imap.clear();
                for(int j=i+1,sum = -nums[i];j<=N-1;j++)
                {
                    if(imap[nums[j]]>0)
                    {
                        ret.push_back({nums[i],nums[imap[nums[j]]-1],nums[j]});
                        imap[sum-nums[j]] = imap[nums[j]] = -1;
                    }
                    else if(imap[sum-nums[j]]!=-1)  imap[sum-nums[j]] = j+1;
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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