Easy

题目描述

给你两个整数数组 nums1 和 nums2，大小分别为 n 和 m。计算下列值：

  • answer1：满足 nums1[i] 存在于 nums2 中的下标 i 的数量。
  • answer2：满足 nums2[i] 存在于 nums1 中的下标 i 的数量。

返回 [answer1, answer2]。

示例 1：

输入：nums1 = [2,3,2], nums2 = [1,2]
输出：[2,1]

示例 2：

输入：nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
输出：[3,4]
解释：
nums1 中下标 1、2、3 处的元素在 nums2 中也存在。所以 answer1 是 3。
nums2 中下标 0、1、3、4 处的元素在 nums1 中存在。所以 answer2 是 4。

示例 3：

输入：nums1 = [3,4,2,3], nums2 = [1,5]
输出：[0,0]
解释：
nums1 和 nums2 之间没有公共数字，所以答案是 [0,0]。

约束条件：

  • n == nums1.length
  • m == nums2.length
  • 1 <= n, m <= 100
  • 1 <= nums1[i], nums2[i] <= 100

解题思路

这道题要求统计两个数组中互相包含的元素个数。有两种常见解法：

方法一：暴力查找 对于 nums1 中的每个元素，遍历 nums2 查找是否存在；对于 nums2 中的每个元素，遍历 nums1 查找是否存在。时间复杂度为 O(n×m)。

方法二：哈希表优化（推荐） 将两个数组分别转换为哈希集合，然后遍历原数组检查元素是否在对应的集合中。这样避免了重复的线性查找，时间复杂度优化为 O(n+m)。

具体步骤：

  1. 将 nums1 和 nums2 转换为集合 set1 和 set2
  2. 遍历 nums1，统计在 set2 中存在的元素个数
  3. 遍历 nums2，统计在 set1 中存在的元素个数
  4. 返回两个计数结果

虽然数据范围较小，但哈希表解法在代码实现上更加清晰，且具有更好的时间复杂度。

代码实现

class Solution {
public:
    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        
        int answer1 = 0, answer2 = 0;
        
        for (int num : nums1) {
            if (set2.count(num)) {
                answer1++;
            }
        }
        
        for (int num : nums2) {
            if (set1.count(num)) {
                answer2++;
            }
        }
        
        return {answer1, answer2};
    }
};

class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        
        answer1 = sum(1 for num in nums1 if num in set2)
        answer2 = sum(1 for num in nums2 if num in set1)
        
        return [answer1, answer2]

public class Solution {
    public int[] FindIntersectionValues(int[] nums1, int[] nums2) {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        
        int answer1 = 0, answer2 = 0;
        
        foreach (int num in nums1) {
            if (set2.Contains(num)) {
                answer1++;
            }
        }
        
        foreach (int num in nums2) {
            if (set1.Contains(num)) {
                answer2++;
            }
        }
        
        return new int[] {answer1, answer2};
    }
}

var findIntersectionValues = function(nums1, nums2) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    
    let answer1 = 0, answer2 = 0;
    
    for (const num of nums1) {
        if (set2.has(num)) {
            answer1++;
        }
    }
    
    for (const num of nums2) {
        if (set1.has(num)) {
            answer2++;
        }
    }
    
    return [answer1, answer2];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度哈希表解法暴力解法
时间复杂度O(n + m)O(n × m)
空间复杂度O(n + m)O(1)

其中 n 和 m 分别是 nums1 和 nums2 的长度。哈希表解法需要额外的空间存储集合，但时间效率更高。