LeetCode题解之 3Sum

1、题目描述

2、问题分析

使用hashtable 的方法做，解法不是最优的，思路简单直观。

3、代码

vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result ;
     
        if( nums.size()  < 3 ){
            return result ;
        }  
        
        sort(nums.begin() ,nums.end());
        map<int,int> m;
        for( int i = 0;i <nums.size() ; ++i){
            m[nums[i]] = i;
        }
        
        for( int i = 0; i < nums.size() - 2; ++i){
            if( i > 0 && nums[i]  == nums[i-1] ) continue;
            for( int j = i+1; j < nums.size() - 1; j++ ){
                if( j > i+1 && nums[j] == nums[j-1]) continue ;
                auto it = m.find( -(nums[i] + nums[j]) );
                if( it != m.end() && it->second > j ){
                    vector<int> r{nums[i],nums[j],it->first};
                    result.push_back( r );
                }
            }
        }
        
        return result;
        
    }