3Sum Closest Problem:(C++,平均时间复杂度小于O(n^2))


  • 0
    R
    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            std::sort(nums.begin(),nums.end());//使用STL的sort对nums进行排序
            int min=nums.at(0)+nums.at(1)+nums.at(2);  //初始化closest value
            for(int i=0;i<nums.size()-2;i++){
                int L=i+1,R=nums.size()-1;//左游标   右端点游标
                while(L<R){
                    int temp=nums.at(i)+nums.at(L)+nums.at(R);
                    if(abs(temp-target)<=abs(min-target))//当前更近
                        min=temp;
                    if(temp<target){  //小于目标值
                        L++;
                    }else if(temp>target){ //大于目标值
                        R--;
                    }else{  //等于目标值
                        return target;
                    }
                    while(L<(R-1)&&nums.at(L)==nums.at(L+1)){  //处理相同的左游标数
                        L++;
                    }
                    while((L+1)<R&&nums.at(R)==nums.at(R-1)){  //处理相同的右游标数
                        R--;
                    }
                }
                while(i<(nums.size()-2)&&nums.at(i)==nums.at(i+1)){  //处理相同的数
                    i++;
                }
            }
            return min;
            
        }
    };
    

Log in to reply
 

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