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 协议》，转载必须注明作者和本文链接