350.intersection-of-two-arrays-ii.md

問題

https://leetcode.com/problems/intersection-of-two-arrays-ii/

回答

初回の回答:

２つの配列の共通部分を抽出する問題。しかし、同じ数字であっても別個の共通部分としてカウントする。$[1,2,2,1]$と $[2,2]$ の共通部分は $[2,2]$ といった感じ。これは解けなかったので答え見た。

1. HashMap を使い、片方の配列の 要素 => 要素数 をデータとして持つ。そしてもう片方の要素をループで回して、ヒットするたびに result にプッシュしていく方法。
2. 両方の配列をまずソートし、左から順に要素を比較していく方法（下記実装参照）。

自分は 2 の方を採用して実装してみた。

impl Solution {
    pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        // this needs to be implemented by yourself, not calling a built-in method.
        let mut nums1_ = nums1.clone();
        let mut nums2_ = nums2.clone();
        nums1_.sort();
        nums2_.sort();

        let mut i = 0;
        let mut j = 0;
        let mut result = Vec::new();
        while i < nums1_.len() && j < nums2_.len() {
            let nums1_i = nums1_[i];
            let nums2_j = nums2_[j];
            if nums1_i == nums2_j {
                result.push(nums1_i);
                i += 1;
                j += 1;
            } else if nums1_i < nums2_j {
                i += 1;
            } else if nums1_i > nums2_j {
                j += 1;
            }
        }
        result
    }
}