3、查找表相关问题

lidong / 2023-05-08 / 原文

1、两类查找问题

1.1、两个数组的交集

349 - 两个数组的交集

public static int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums1) set.add(i);

    Set<Integer> res = new HashSet<>();
    for (int i : nums2) {
        if (set.contains(i)) res.add(i);
    }

    return res.stream().mapToInt(Integer::intValue).toArray();
}

1.2、两个数组的交集 II

350 - 两个数组的交集 II

public static int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : nums1) map.put(i, map.getOrDefault(i, 0) + 1);

    List<Integer> list = new ArrayList<>();
    for (int i : nums2) {
        if (map.getOrDefault(i, 0) != 0) {
            list.add(i);
            map.put(i, map.get(i) - 1);
        }
    }

    return list.stream().mapToInt(Integer::intValue).toArray();
}

2、Set 和 Map 不同底层实现的区别

3、更多题目

242 - 有效的字母异位词
202 - 快乐数
290 - 单词规律
205 - 同构字符串
451 - 根据字符出现频率排序

4、两数之和

1 - 两数之和

public static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) return new int[]{i, map.get(complement)};
        else map.put(nums[i], i);
    }

    throw new IllegalArgumentException("The input has no solution");
}