typedef std::unordered_map<int,vector<int>> umap; 
class Solution {
private:
        vector<vector<int>> result;
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3) return result;
        sort(nums.begin(),nums.end());
        umap num_idx_map;
        int i,j,l,r,max;
        for(i=0;i<nums.size()&&nums[i]<0;i++);
        for(;i<nums.size();i++){
            auto it=num_idx_map.find(nums[i]);
            if(it==num_idx_map.end()){
                vector<int> tmp;
                tmp.push_back(i);
                num_idx_map.insert(umap::value_type(nums[i],tmp));
            }else{
            it->second.push_back(i);}
        }
        for(i=0;i<nums.size()-2&&nums[i]<=0;i++){
            for(j=i+1;j<nums.size()-1;j++){
               auto it=num_idx_map.find(0-nums[i]-nums[j]);
               if(it!=num_idx_map.end()){
                   for(int k=it->second.size()-1;((it->second[k])>j);k--){
                       vector<int> tmp(3);
                       tmp[0]=nums[i];tmp[1]=nums[j];tmp[2]=0-tmp[0]-tmp[1];
                       //if(find(result.begin(),result.end(),tmp)==result.end()){
                        result.push_back(tmp);
                        //cout<<"repeat"<<endl;
                        break;
                       //}
                   }
               }
               while(nums[j+1]==nums[j])j++;
            }
            while(nums[i+1]==nums[i])i++;
        }
        return result;
    }
 };

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据