🚀

LeetCode 2215. Find the Difference of Two Arrays - ハッシュセットへの変換

2025/09/04に公開

LeetCode

tech

2215. Find the Difference of Two Arrays

Intution

nums1とnums2の重複がある場合に削除して、それぞれ新しい配列を作るようにする
- 共通配列を作って差分をとればいいのではないか。

ruby

  def find_difference(nums1, nums2)
    c = nums1 & nums2
    [(nums1 - c).uniq, (nums2 - c).uniq]
end

こちらのSolutionがより簡単でした。共通配列を作る一手が不要となる。

def find_difference(nums1, nums2)
    [(nums1 - nums2).uniq, (nums2 - nums1).uniq]
end

python

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        ans1 = []
        ans2 = []
        for n1 in nums1:
            if n1 not in nums2:
                ans1.append(n1)

        for n2 in nums2:
            if n2 not in nums1:
                ans2.append(n2)

        return list(set(ans1)), list(set(ans2))

for n1 in nums1: のループ内で if n1 not in nums2: のチェックを行っています。このnot in演算子は、リストに対して使うと、最悪の場合でリストの長さ分の時間がかかります。つまり、O(n)の計算量。

Approach

ハッシュセットを利用する。

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1 = set(nums1)
        set2 = set(nums2)

        return list(set1-set2), list(set2-set1)

typescript

Setの差集合は提供されていないため、filter()とhas()で差集合を計算する。

function findDifference(nums1: number[], nums2: number[]): number[][] {
    const set1 = new Set<number>(nums1)
    const set2 = new Set<number>(nums2)

    return [
        [...set1].filter(x => !set2.has(x)),
        [...set2].filter(x => !set1.has(x))
    ]
};

golang

func findDifference(nums1 []int, nums2 []int) [][]int {
    set1 := map[int]bool{}
    set2 := map[int]bool{}
    for _, n := range nums1 {
        set1[n] = true
    }
    for _, n := range nums2 {
        set2[n] = true
    }

    diff1, diff2 := []int{}, []int{}
    for k := range set1 {
        if !set2[k] {
            diff1 = append(diff1, k)
        }
    }
    for k := range set2 {
        if !set1[k] {
            diff2 = append(diff2, k)
        }
    }

    return [][]int{diff1, diff2}
}

重複排除: リストからハッシュセットを作成する際に、重複する要素は自動的に上書きされるため、一意な要素の集合を取得。
要素の存在チェック: ハッシュセットでの存在チェックは、平均してO(1)で完了。これに対し、リストでのチェックは線形探索になり、O(n)かかる。

学習のポイント

ハッシュセットの存在チェックはO(1)で完了する。

2215. Find the Difference of Two Arrays

Intution

Approach

学習のポイント

Discussion