代码随想录算法训练营第六天 | leetcode:四数相加II, 赎金信 , 三数之和 , 四数之和

Problem: 454. 四数相加 II

解题方法

  1. 与两数之和类似:使用哈希对照组 $hash,构建以 nums 的值作为对照组的 key,值为 nums 的 key 哈希对照组。再次循环遍历 nums, 寻找 hash 对照组中 key + 循环中 nums 值 = target 的值。即:$hash [$target-$val] 存在,则返回 $hash [$target-$val] 与循环中的 key 值。
  2. 不同的点在于四数相加,需要把两两数组看成一个整体。类比成一个两数相加的效果。

复杂度

时间复杂度:

O(n)

空间复杂度:

O(1)

code

  /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $hash = [];
        //$nums1, $nums2构建成哈希对照组
        foreach($nums1 as $key1 => $val1){
            foreach($nums2 as $key2 => $val2){
                $hash[$val1 + $val2]++;
            }
        }
        $count = 0;
        //$nums3, $nums4作为整体与对照组相加等于0 即:0-($val3 + $val4)等于对照组内数据
        foreach($nums3 as $key3 => $val3){
            foreach($nums4 as $key4 => $val4){
                if(isset($hash[0-($val3 + $val4)])){
                    $count += $hash[0-($val3 + $val4)];
                }
            }
        }
        return $count;
    }

Problem: 383. 赎金信

解题方法

这题比较简单,经典的哈希场景应用,判断 ransomNote 能不能由 magazine 里面的字符构成,也就是快速判断一个元素是否出现集合里。

复杂度

时间复杂度:

O(n)

空间复杂度:

O(1)

code

 /**
     * @param String $ransomNote
     * @param String $magazine
     * @return Boolean
     */
    function canConstruct($ransomNote, $magazine) {
        if(strlen($magazine) < strlen($ransomNote)){
            return false;
        }

        $hash = [];
        for($i = 0; $i < strlen($ransomNote); $i++){
            $hash[$ransomNote[$i]]++;
        }
        for($j = 0; $j < strlen($magazine); $j++){
            if($hash[$magazine[$j]]){
                $hash[$magazine[$j]]--;
            }
        }
        if(array_sum($hash) == 0){
            return true;
        }
        return false;
    }

Problem: 15. 三数之和

需要注意的问题

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

解题方法

  1. 本题采用双指针而不是哈希法。题目中说的不可以包含重复的三元组。把符合条件的三元组放进hash中,然后再去重,这样是非常费时的,很容易超时。并且去重的过程不好处理。
  2. 双指针解法(其实感觉叫三指针也行),先将给定数组从小到大排序。定义遍历数据指针i初始化指向0,以及left指针i+1,right指针size-1。当i指针遍历数组是left与right指针同时相向而行,寻找 nums[i] + nums[left] + nums[right] = 0 的值。因为数组从小到大排序的,所以当nums[i] + nums[left] + nums[right] > 0时,需要right–,缩小相加和。当nums[i] + nums[left] + nums[right] < 0时。,right–是缩小相加和的操作。需要left++, 增加相加和。直到把所有nums[i] + nums[left] + nums[right] = 0 的值收集完毕。

复杂度

时间复杂度:

O(n*n)

空间复杂度:

O(1)

code

class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums)
    {
        $len = count($nums) - 1;
        $res = [];
        sort($nums);
        foreach ($nums as $key => $val) {
            //剪枝操作 排序后左边 > 0的话  后面全都大于0不用遍历了
             if ($val > 0) {
                return $res;
            }
            //去重操作,$key > 0 防止越界,此处使用key-1做比较,是因为指针往右移动,left刚好在key后一位,使用key+1操作,容易把key,left的合理组合剔除掉
            if ($key > 0 && $val == $nums[$key - 1]) {
                continue;
            }
            //定义左右指针
            $left = $key + 1;
            $right = $len;

            while ($left < $right) {
                //因为排序过的结果,所以判断大于0,right指针--就是和缩小的操作,left++是和扩大的操作
                if ($val + $nums[$left] + $nums[$right] > 0) {
                    $right--;
                } elseif ($val + $nums[$left] + $nums[$right] < 0) {
                    $left++;
                } else {
                    //收集结果
                    $res[] = [$val , $nums[$left] , $nums[$right]];
                    //收集结果后去重,此处while结束之后,left指针指向left + 1,right指针指向right + 1,
                    //此时left,right,与上面收集过的结果集还是相等的,所以下面还需要进行left++, right--的操作
                    //否则进入死循环,一直收集相同的结果。
                    while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;
                    while ($left < $right && $nums[$right] == $nums[$right - 1]) $right--;
                    $left++;
                    $right--;
                }
            }
        }
        return $res;
    }
}

Problem: 18. 四数之和

需要注意的问题

  1. 答案中不可以包含重复的四元组。
  2. 与三数之和不同 target不等于0,数据剪枝操作会有不同

解题方法

与三数之和的解法相同,只是加一层循环i。在二层循环k中,需要把i+k看成整体做剪枝操作。

复杂度

时间复杂度:

O(nnn)

空间复杂度:

O(1)

code

class Solution {

/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer[][]
 */
function fourSum($nums, $target) {
    $res = [];
    sort($nums);
    for($i = 0; $i < count($nums); $i++){
        //第一层剪枝操作,去除不必要的遍历
        if($nums[$i] > $target && $nums[$i] >= 0){
            break;
        }
        //第一层去重操作,需要保证i>0,避免$i-1越界
        if($i > 0 && $nums[$i] == $nums[$i-1]){
            continue;
        }
        for($k = $i + 1; $k < count($nums)-1; $k++){
            //二级剪枝操作
            if($nums[$i] + $nums[$k] > $target && $nums[$i] + $nums[$k] >= 0){
                break;
            }
            //第二层去重操作,需要保证$k> $i + 1,避免$k-1越界
            if($k > $i + 1 && $nums[$k] == $nums[$k-1]){
                continue;
            }
            $left = $k + 1;
            $right = count($nums) - 1;
            while($left < $right){
                //因为排序过的结果,所以判断大于target,right指针--就是和缩小的操作,left++是和扩大的操作
                $sum = $nums[$i] + $nums[$k] + $nums[$left] + $nums[$right];
                if($sum > $target){
                    $right--;
                }elseif($sum < $target){
                    $left++;
                }else{
                    //收集结果
                    $res[] = [$nums[$i] , $nums[$k] , $nums[$left] , $nums[$right]];
                     //收集结果后去重,此处while结束之后,left指针指向left + 1,right指针指向right + 1,
                    //此时left,right,与上面收集过的结果集还是相等的,所以下面还需要进行left++, right--的操作
                    //否则进入死循环,一直收集相同的结果。
                    while($left < $right && $nums[$left] == $nums[$left + 1]){
                        $left++;
                    }
                    while($left < $right && $nums[$right] == $nums[$right - 1]){
                        $right--;
                    }
                    $left++;
                    $right--;
                }
            }
        }
    }
    return $res;
}

}



本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!