给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析：本题算法比较简单，主要考点是算法的时间复杂度

思路1：三次遍历，选取所有的[a,b,c]组合判断是否满足条件，时间复杂度为O（n^3）.这种思路显然在时间上就过不了.

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        sort($nums);
        $length=3;
        $arr=array();
        if(count($nums)==$length&&array_sum($nums)===0){
            array_push($arr,$nums);
        }
        for($i=0;$i<count($nums)-$length-1;$i++){//循环整个数组(不包括最后两个元素)
            for($j=$i+1;$j<count($nums)-1;$j++){
                for($k=$j+1;$k<count($nums);$k++){
                    $subArr=array();
                    array_push($subArr,$nums[$i]);
                    array_push($subArr,$nums[$j]);
                    array_push($subArr,$nums[$k]);
                    if(array_sum($subArr)===0){
                        array_push($arr,$subArr);
                    }
                }
            }
        }
        return $arr;
    }

结果:

思路2: 以0为分界点,将数组分成大于0和小于0以及0三部分.这样可能出现的解答为[a,b,c],[a,0,b],[0,0,0]三大类，数组长度变短后遍历时所需时间也会变少,时间复杂度小于O（n^3）（具体是多少我也不会推导。。）

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        sort($nums);//排序
        $length=3;
        $arr=array();
        $negatives=array();
        $zeros=array();
        $positives=array();
        for($i=0;$nums[$i]<0;$i++){//取出负数
            array_push($negatives,$nums[$i]);
        }
        for($i=0;$i<count($nums)&&$nums[$i]<1;$i++){//取出零
            if($nums[$i]===0){
                array_push($zeros,$nums[$i]);
            }
        }
        for($i=(count($nums)-1);$nums[$i]>0;$i--){//取出正数
            array_push($positives,$nums[$i]);
        }
        for($i=0;$i<count($negatives);$i++){//遍历负数
            if($i<count($negatives)-1){
                for($j=$i+1;$j<count($negatives);$j++){
                    if(in_array(0-($negatives[$i]+$negatives[$j]),$positives)){//[a,b,c]模式
                        array_push($arr,array($negatives[$i],$negatives[$j],0-($negatives[$i]+$negatives[$j])));
                    }
                }
            }
            if(in_array(0-$negatives[$i],$positives)&&count($zeros)>0){//[a,0,b]模式
                array_push($arr,array($negatives[$i],0,0-$negatives[$i]));
            }

        }

        for($i=0;$i<count($positives)-1;$i++){//遍历正数
            for($j=$i+1;$j<count($positives);$j++){
                if(in_array(0-($positives[$i]+$positives[$j]),$negatives)){//[a,b,c]模式
                    array_push($arr,array($positives[$i],$positives[$j],0-($positives[$i]+$positives[$j])));
                }
            }
        }
        if(count($zeros)>=3){//[0,0,0]模式
            array_push($arr,array(0,0,0));
        }
        //去重复
        $temp=array();
        foreach ($arr as $v){
            $v=join(',',$v); //降维,也可以用implode,将一维数组转换为用逗号连接的字符串
            $temp[]=$v;
        }
        $temp=array_unique($temp); //去掉重复的字符串,也就是重复的一维数组
        foreach ($temp as $k => $v){
            $temp[$k]=explode(',',$v); //再将拆开的数组重新组装
        }

        return $temp;
    }
    
}

结果:

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客