Leetcode基础刷题之PHP解析(16. 3Sum Closest)

 2019-6-25 星期三 开始吧

上一题链接Leetcode基础刷题之PHP解析(15. Longest Common Prefix)

题目描述

给定一组数组和一个目标数，求三个数加起来最接近目标数的和，只有唯一的一组解。

题目分析

和上一题是有点像的。因为给定的数组无序，为了方便判断先进行排序。我们先随便设置一个参照数(比如我先求出数组前三位的和)，有什么作用呢？方便之后的循环中求出的解减去目标数的绝对值和参照数的值减去目标值的绝对值进行比较，谁的绝对值小，说明更接近目标数，这样保证了每一轮我们的参照数都是最接近目标值的，剩下的操作和昨天一样，一个往左一个往右，向中间不断地缩短数组元素，直到结束，返回参照数, 或者中间有值等于目标数直接返回目标数,0距离感。

 /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function threeSumClosest($nums, $target) {
        sort($nums);
        $result=$nums[0]+$nums[1]+$nums[2];
        for($i=0;$i<count($nums)-2;$i++){
            if($i>0 && $nums[$i]==$nums[$i-1]) continue;
            $l=$i+1;
            $r=count($nums)-1;
            while($l<$r){
                $temp=$nums[$i]+$nums[$l]+$nums[$r];
                if(abs($target-$temp)<abs($result-$target)){
                    $result=$temp;
                }
                if($temp==$target) return $target;
                elseif($temp<$target) $l ++;
                else $r --;
            }
        }
        return $result;
    }