美文网首页
[M]Leetcode-16-3Sum Closest

[M]Leetcode-16-3Sum Closest

作者: glassyw | 来源:发表于2017-10-25 10:27 被阅读19次

    思路:

    类似3sum/2sum利用双指针。
    不同在于,这里只要计算总和就可以了,这部分更加简单。
    总体的思路是:
    先预先排序,加快搜索速度。
    确定left,然后用mid/right扫描数组。
    当总和与target的距离变小时,更新数据。
    接着,如果正好==target 直接返回,如果>target ,说明大了,right--,反之,mid++。

    注意:

    1.返回值mmin初始化最好是nums[0]+nums[1]+nums[2],因为可能会出现只有三个元素的情况。如果不这样处理,后面可能不会执行mmin的更新。(即返回的可能是你的其他初始值)
    2.要考虑sum==target的情况。如果一开始就处理这个可能性,不要忘了mid和right经过调整后也会出现这种情况,比较优雅的写法是直接放在while(mid<right)作为第三种情况处理。

    代码:(C++)

    int threeSumClosest(vector<int>& nums, int target) {
        int mmin=nums[0]+nums[1]+nums[2]; //debug:mmin需要初始化,因为下面有限制条件才跳进去更新,如果正好是三个数且正好符合就会遗漏 
        int len=nums.size();
         
        sort(nums.begin(),nums.end());  
        for(int left=0;left<len-2;left++){ 
            int mid=left+1;
            int right=len-1;
                
            while(mid<right){
                int tmp_sum=nums[left]+nums[mid]+nums[right];
                
                //距离更近了,就更新记录 
                if(abs(target-tmp_sum)<abs(target-mmin)){
                    mmin=tmp_sum;   
                }
                
                if(tmp_sum<target){  //太少了,mid往右移 
                    mid++;
                }else if(tmp_sum>target){  //太多了,right往左移 
                    right--;
                }else{                      //debug:这部分不能放在上面,因为有可能在调整了指针后也会正好符合的情况。 
                    mmin=nums[left]+nums[mid]+nums[right];
                    return mmin;
                }
            }
            
        }
        
        return mmin;
    }
    
    

    相关文章

      网友评论

          本文标题:[M]Leetcode-16-3Sum Closest

          本文链接:https://www.haomeiwen.com/subject/ehzfpxtx.html