class Solution {
private:
        vector<vector<int>> result;
        int repeat=0;
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3) return result;
        sort(nums.begin(),nums.end());
        multimap<int,int> left_map,right_map;
        int zero_idx=find_closzt(nums,0);
        int i,left=0,right=nums.size()-1;
        for(i=0;(i<=zero_idx||(nums[i]==nums[zero_idx]&&i<nums.size()));i++){
            left_map.insert(make_pair(nums[i],i));
        }
        for(;i<nums.size();i++){
            right_map.insert(make_pair(nums[i],i));
        }
        for(auto n: nums){
            if(n>=0){
                find_two_sum(left_map,n);
            }else{
                find_two_sum(right_map,n);
            }
        }
        return result;
    }
    void find_two_sum(multimap<int,int> &nums,int sum){
        for(auto num:nums){
            auto it=nums.find(0-sum-num.first);
            if(it!=nums.end()&&*it!=num){
                vector<int> tmp(3);
                if(sum>0){
                    tmp[2]=sum;
                    if(it->first<num.first){
                        tmp[0]=it->first;
                        tmp[1]=num.first;
                    }else{
                        tmp[1]=it->first;
                        tmp[0]=num.first;
                    }
                }else{
                    tmp[0]=sum;
                    if(it->first<num.first){
                        tmp[1]=it->first;
                        tmp[2]=num.first;
                    }else{
                        tmp[2]=it->first;
                        tmp[1]=num.first;
                    }
                }
                //if(find(result.begin(),result.end(),tmp)==result.end()){
                    result.push_back(tmp);
                    
                //}else{
                  //      repeat++;
                //}
            }
        }
    }
    int find_closzt(vector<int>& nums,int target){
        if(nums.size()==0) return -1;
        if(nums.size()==1) return 0;
        if(nums.size()==2) return abs(nums[0]-target)>abs(nums[1]-target)?1:0;
        int left=0,mid=nums.size()/2,right=nums.size()-1;
        int err=abs(nums[mid]-target);
        while(left<right&&left<mid &&mid <right){
            if(nums[mid]<target){
                left=mid;mid=(left+right)/2;continue;
            }
            if(nums[mid]>target){
                right=mid;mid=(left+right)/2;continue;
            }
            return mid;
        }
        if(left==0){
            return abs(nums[0]-target)>abs(nums[1]-target)?1:0;
        }
        if(left==nums.size()-1){
            return abs(nums[nums.size()-1]-target)>abs(nums[nums.size()-2]-target)?nums.size()-2:nums.size()-1;
        }
        if(abs(nums[left]-target)>abs(nums[left+1]-target)){
            if(abs(nums[left+1]-target)>abs(nums[left-1]-target)) {
                return left-1;
            }else{
                return left+1;
            }
        }else{
            if(abs(nums[left]-target)>abs(nums[left-1]-target)) {
                return left-1;
            }else{
                return left;
            }
        }
    }
};

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

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