讨论/《哈希表》 - 两个数组的交集 II/
《哈希表》 - 两个数组的交集 II
共 3 个回复

JavaScript版本~

执行用时:80 ms, 在所有 JavaScript 提交中击败了93.88%的用户
内存消耗:39.5 MB, 在所有 JavaScript 提交中击败了49.89%的用户

用哈希表存储较短的数组

var intersect = function (nums1, nums2) {
    if(nums1.length > nums2.length) return intersect(nums2, nums1)
    const map = {}, result = []
    for (let i = 0; i < nums1.length; i++) {
        if(!map[nums1[i]]) map[nums1[i]] = 1
        else map[nums1[i]] = ++ map[nums1[i]]
    }
    for (let i = 0; i < nums2.length; i++) {
        if (map[nums2[i]] >= 1) {
            result.push(nums2[i])
            map[nums2[i]] = -- map[nums2[i]]
        }
    }
    return result
};

双指针版本, 需要先排好序,两个指针从索引0开发分别指向nums1, nums2, 如果相同就添加到result数组, 不同就小的那个指针前进一步

var intersect = function (nums1, nums2) {
    nums1.sort((a, b) => a - b)
    nums2.sort((a, b) => a - b)
    console.log(nums1, nums2)
    const result = []
    let i = 0, j = 0    //定义i为nums1的指针, j 为nums2 的指针
    while(i <= nums1.length - 1 && j <= nums2.length - 1) {
        if(nums1[i] === nums2[j]) { //如果两个数字相同
            result.push(nums1[i])
            i++
            j++
        }else {
            if(nums1[i] < nums2[j]) i++
            else j++
        }
    }
    return result
};
1
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hashMap1;
        vector<int> res;

        for (int i = 0; i < nums1.size(); i++) {
            hashMap1[nums1[i]] += 1;
        }

        for (int i = 0; i < nums2.size(); i++) {
            if (hashMap1.count(nums2[i]) && hashMap1[nums2[i]] > 0) {
                res.push_back(nums2[i]);
                hashMap1[nums2[i]] -= 1;
            }
        }

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