【算法】两个数组的交集

题目概述

描述:
给定两个整数数组分别为nums1, nums2,找到它们的公共元素并按返回。
数据范围：
1≤nums1.length,nums2.length≤10001≤nums1.length,nums2.length≤1000
1≤nums1[i],nums2[i]≤1000
1≤nums1[i],nums2[i]≤1000

算法原理

核心思想:哈希

题目给定的数字范围为[1,1000],
我们就以一个长度为1001(大于1000就OK)的boolean类型的数组,来模拟哈希,
先遍历nums1中所有的元素,将boolean数组中对应nums1元素的下标值更改为true,然后再遍历nums2,如果nums2中元素对应的哈希数组下标值为true,则说明出现过,添加到返回结果的数组中即可

注意事项:
题目示例2中的返回值没有重复元素,就说明出现相同的值是最终只添加一个,所以我们需要在nums2加入结果之后将该值从哈希数组中删除

代码详解

public class Solution {
    public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer>nums2) {
        boolean[] hash = new boolean[1001];
        for(int x : nums1){//遍历nums1
            hash[x] = true;//将对应元素在hash中的下标值标记为true
        }
        ArrayList<Integer> ret = new ArrayList<>(); 
        for(int x : nums2){//遍历nums2
            if(hash[x]){//如果该元素对应hash中下标值为true,就说明已经出现过了
                ret.add(x);
                hash[x]=false;//添加完后删除,防止元素重复出现
                
            }
        }

        return ret;

    }
}

如果文章对客官有帮助的话,麻烦点赞关注走一走,感谢支持~~~