問題概要：350. 二つの配列の交差

与えられた二つの整数配列から、両方に含まれる要素を重複を考慮して返す。各要素の出現回数は、両方の配列で最小となる回数に制限される。

手法1: ハッシュマップによるカウント

一方の配列の要素とその頻度をハッシュマップに保存し、もう一方の配列を走査しながら該当する要素があれば結果リストに追加し、頻度を減算する。

• 時間計算量: O(n + m) — n, m はそれぞれ配列の長さ
• 空間計算量: O(min(n, m)) — より小さい配列の要素数に依存

class Solution {
public:
    std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
        std::unordered_map<int, int> count;
        for (int val : nums1) {
            count[val]++;
        }
        std::vector<int> result;
        for (int val : nums2) {
            if (count[val] > 0) {
                result.push_back(val);
                count[val]--;
            }
        }
        return result;
    }
};

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int val : nums1) {
            freq.merge(val, 1, Integer::sum);
        }
        List<Integer> result = new ArrayList<>();
        for (int val : nums2) {
            int current = freq.getOrDefault(val, 0);
            if (current > 0) {
                freq.merge(val, -1, Integer::sum);
                result.add(val);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

func intersect(nums1 []int, nums2 []int) []int {
    freq := make(map[int]int)
    for _, val := range nums1 {
        freq[val]++
    }
    var result []int
    for _, val := range nums2 {
        if freq[val] > 0 {
            freq[val]--
            result = append(result, val)
        }
    }
    return result
}

手法2: 双方向ポインタ法（ソート済み配列対応）

両方の配列を昇順に並べた上で、二つのポインタを用いて同時に走査。値が一致すれば結果に追加し、どちらかが小さい場合はそのポインタを進める。

• 時間計算量: O(n log n + m log m) — ソート処理が支配的
• 空間計算量: O(1) — 結果を除く追加メモリは不要（入力変更を許容する場合）

class Solution {
public:
    std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;
        std::vector<int> result;
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                result.push_back(nums1[i]);
                i++;
                j++;
            }
        }
        return result;
    }
};

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                result.add(nums1[i]);
                i++;
                j++;
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

func intersect(nums1 []int, nums2 []int) []int {
    slices.Sort(nums1)
    slices.Sort(nums2)
    i, j := 0, 0
    var result []int
    for i < len(nums1) && j < len(nums2) {
        switch {
        case nums1[i] < nums2[j]:
            i++
        case nums1[i] > nums2[j]:
            j++
        default:
            result = append(result, nums1[i])
            i++
            j++
        }
    }
    return result
}