# 前言

利用 LeetCode 磨練演算法

# 題目連結

4Sum II - LeetCode

# 解題思路

# 暴力解法

暴力解法就是跑四層 loop，如下 solution code

<?php
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $count = 0;
        $len = count($nums1);
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                for ($k = 0; $k < $len; $k++) {
                    for ($l = 0; $l < $len; $l++) {
                        if ($nums1[$i] + $nums2[$j] + $nums3[$k] + $nums4[$l] === 0) {
                            $count++;
                        }
                    }
                }
            }
        }

        return $count;
    }
}

時間複雜度為 O(N 的四次方)，空間複雜度為 O(1)

# Dictionary

• 跑一個 double loop，取得 $nums1 & $nums2 的 sum & sum’s count，並記在一個 dictionary as key (sum) => count (sum 出現的次數)
• 跑第二個 double loop，先取得 $nums3 & $nums4 的 sum，並取得 diff (0 — sum)
• diff 代表 $nums3 + $nums4 的 sum，要再加 diff 會等於 0
• 如果 nums1 & nums2 dictionary 中存在 diff 的話，那就代表 nums1 + nums2 + nums3 + nums4 會等於 0，所以要加上 count
• 假如 key => value 是 -2 => 3 的話，那在 nums3 & nums4 loop 中只要 diff 有出現 -2 的話，那就要 count += 3
• 假如 nums1 & nums2 的 dictionary 中， -2 => 3，則可能的組合如下
• nums1[1] + nums2[1] = -2
• nums1[1] + nums2[2] = -2
• nums2[2] + nums2[1] = -2
• 所以當 nums3[1] + nums4[2] = 2，那就是 count += 3
• nums1[1] + nums2[1] + nums3[1] + nums4[2] = 0
• nums1[1] + nums2[2] + nums3[1] + nums4[2] = 0
• nums2[2] + nums2[1] + nums3[1] + nums4[2] = 0

solution code 如下：

<?php
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $count = 0;
        $len = count($nums1);
        $nums12Dic = [];

        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                $nums12Dic[$nums1[$i] + $nums2[$j]]++;
            }
        }

        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                $sum = $nums3[$i] + $nums4[$j];
                $diff = 0 - $sum;

                if (isset($nums12Dic[$diff])) {
                    $count += $nums12Dic[$diff];
                }
            }
        }

        return $count;
    }
}

時間複雜度為 O(N 的平方)

空間複雜度為 O(N 的平方)