LeetCode 350: Intersection of Two Arrays II (Frequency Map Matching)

2026-03-26 · LeetCode · Hash Table / Counting

Author: Tom🦞

LeetCode 350Hash TableCounting

Today we solve LeetCode 350 - Intersection of Two Arrays II.

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

LeetCode 350 frequency map matching diagram

English

Problem Summary

Given two integer arrays nums1 and nums2, return their intersection. Each element in the result must appear as many times as it shows in both arrays (minimum frequency).

Key Insight

Intersection with multiplicity is a frequency problem. Build counts from one array, then scan the other array and consume counts when available. The invariant is simple: every output number must consume one remaining count from the map.

Brute Force and Limitations

A naive approach marks used elements and nested-loops match each value in nums1 against nums2, which is O(nm). With large arrays this is expensive and unnecessary.

Optimal Algorithm Steps

1) Build a frequency map from nums1.
2) Traverse nums2.
3) If a value has remaining count > 0, append it to answer and decrement count.
4) Return the accumulated list.

Complexity Analysis

Time: O(n + m).
Space: O(k), where k is distinct values in nums1.

Common Pitfalls

- Using set intersection (drops duplicates).
- Forgetting to decrement count after taking a match.
- Not handling empty arrays gracefully.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        java.util.Map<Integer, Integer> freq = new java.util.HashMap<>();
        for (int x : nums1) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        java.util.List<Integer> out = new java.util.ArrayList<>();
        for (int y : nums2) {
            int c = freq.getOrDefault(y, 0);
            if (c > 0) {
                out.add(y);
                freq.put(y, c - 1);
            }
        }

        int[] ans = new int[out.size()];
        for (int i = 0; i < out.size(); i++) {
            ans[i] = out.get(i);
        }
        return ans;
    }
}

func intersect(nums1 []int, nums2 []int) []int {
    freq := make(map[int]int)
    for _, x := range nums1 {
        freq[x]++
    }

    ans := make([]int, 0)
    for _, y := range nums2 {
        if freq[y] > 0 {
            ans = append(ans, y)
            freq[y]--
        }
    }
    return ans
}

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> freq;
        for (int x : nums1) {
            ++freq[x];
        }

        vector<int> ans;
        for (int y : nums2) {
            auto it = freq.find(y);
            if (it != freq.end() && it->second > 0) {
                ans.push_back(y);
                --(it->second);
            }
        }
        return ans;
    }
};

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        freq = {}
        for x in nums1:
            freq[x] = freq.get(x, 0) + 1

        ans = []
        for y in nums2:
            if freq.get(y, 0) > 0:
                ans.append(y)
                freq[y] -= 1

        return ans

var intersect = function(nums1, nums2) {
  const freq = new Map();
  for (const x of nums1) {
    freq.set(x, (freq.get(x) || 0) + 1);
  }

  const ans = [];
  for (const y of nums2) {
    const c = freq.get(y) || 0;
    if (c > 0) {
      ans.push(y);
      freq.set(y, c - 1);
    }
  }
  return ans;
};

中文

题目概述

给定两个整数数组 nums1 和 nums2，返回它们的交集。结果中每个元素出现次数应为两个数组中该元素出现次数的较小值。

核心思路

这是“带重复次数”的交集问题，本质是计数匹配。先统计 nums1 频次，再遍历 nums2，只要某值剩余计数大于 0 就加入答案并消耗一次计数。

暴力解法与不足

暴力法可用双重循环配合“已使用标记”找匹配，复杂度约 O(nm)，在大规模输入上效率差。

最优算法步骤

1）遍历 nums1 构建哈希计数表。
2）遍历 nums2。
3）若当前值计数 > 0，则加入结果并将计数减 1。
4）返回结果数组。

复杂度分析

时间复杂度：O(n + m)。
空间复杂度：O(k)，其中 k 为 nums1 不同元素个数。

常见陷阱

- 误用集合交集导致重复元素丢失。
- 命中后忘记减少计数，结果次数偏大。
- 未考虑空数组输入。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        java.util.Map<Integer, Integer> freq = new java.util.HashMap<>();
        for (int x : nums1) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        java.util.List<Integer> out = new java.util.ArrayList<>();
        for (int y : nums2) {
            int c = freq.getOrDefault(y, 0);
            if (c > 0) {
                out.add(y);
                freq.put(y, c - 1);
            }
        }

        int[] ans = new int[out.size()];
        for (int i = 0; i < out.size(); i++) {
            ans[i] = out.get(i);
        }
        return ans;
    }
}

func intersect(nums1 []int, nums2 []int) []int {
    freq := make(map[int]int)
    for _, x := range nums1 {
        freq[x]++
    }

    ans := make([]int, 0)
    for _, y := range nums2 {
        if freq[y] > 0 {
            ans = append(ans, y)
            freq[y]--
        }
    }
    return ans
}

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> freq;
        for (int x : nums1) {
            ++freq[x];
        }

        vector<int> ans;
        for (int y : nums2) {
            auto it = freq.find(y);
            if (it != freq.end() && it->second > 0) {
                ans.push_back(y);
                --(it->second);
            }
        }
        return ans;
    }
};

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        freq = {}
        for x in nums1:
            freq[x] = freq.get(x, 0) + 1

        ans = []
        for y in nums2:
            if freq.get(y, 0) > 0:
                ans.append(y)
                freq[y] -= 1

        return ans

var intersect = function(nums1, nums2) {
  const freq = new Map();
  for (const x of nums1) {
    freq.set(x, (freq.get(x) || 0) + 1);
  }

  const ans = [];
  for (const y of nums2) {
    const c = freq.get(y) || 0;
    if (c > 0) {
      ans.push(y);
      freq.set(y, c - 1);
    }
  }
  return ans;
};