哈希映射用法及算法例题

[qingmei2]

哈希映射用法及算法例题

本文为博主算法学习过程中的学习笔记，主要内容来源于其他平台或书籍，出处请参考下方 参考&感谢 一节。

用法

哈希映射 是用于存储 (key, value) 键值对的一种实现。

使用哈希映射的第一个场景是，我们 需要更多的信息，而不仅仅是键。然后通过哈希映射 建立密钥与信息之间的映射关系。

另一个常见的场景是 按键聚合所有信息。我们也可以使用哈希映射来实现这一目标。

例题

1、两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路及实现

HashMap入门的经典题。

简单的方式是使用双层循环进行暴力破解，这种算法时间复杂度为O(N^2)。

而使用HashMap则可以将问题在一层循环中进行解决，时间复杂度仅O(N)：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];
            int find = target - value;
            if (map.containsKey(find) && map.get(find) != i) {
                result[0] = i;
                result[1] = map.get(find);
                break;
            }
            map.put(nums[i], i);
        }
        return result;
    }
}

2、同构字符串

题目描述

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

你可以假设 s 和 t 具有相同的长度。

示例:

输入: s = "egg", t = "add"
输出: true
输入: s = "foo", t = "bar"
输出: false

解题思路及实现

通过2个HashMap存储各自字符对应最初的索引，然后进行比较，当字符对应的最初索引不同时，说明2个字符串不是同构的：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] char1 = s.toCharArray();
        char[] char2 = t.toCharArray();
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        for (int i = 0; i < char1.length; i++) {
            char c1 = char1[i];
            char c2 = char2[i];
            if (!map1.containsKey(c1))
                map1.put(c1, i);
            if (!map2.containsKey(c2))
                map2.put(c2, i);

            if (map1.get(c1) != map2.get(c2))
                return false;
        }
        return true;
    }
}

3、两个列表的最小索引总和

题目描述

https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/

解题思路及实现

这道题的难点是发现映射关系，即 最爱餐厅 -> 索引值 的映射关系。

通过遍历将该映射关系存储到HashMap中后，再次通过一次遍历找出索引值和最小的餐厅，因为索引值最小的情况可能不止一个，因此用一个List进行维护，最终将答案遍历输出：

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap<String, Integer> map = new HashMap<>();
        List<Integer> posList = new ArrayList<>();
        int minPosNum = Integer.MAX_VALUE;

        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }
        for (int i = 0; i < list2.length; i++) {
            String favorite = list2[i];
            Integer position = map.get(favorite);
            if (position != null) {
                int posNum = i + position;
                if (minPosNum > posNum) {
                    minPosNum = posNum;
                    posList.clear();
                    posList.add(i);
                } else if (minPosNum == posNum) {
                    posList.add(i);
                }
            }
        }
        String[] result = new String[posList.size()];
        for (int i = 0; i < posList.size(); i++)
            result[i] = list2[posList.get(i)];
        return result;
    }
}

4、字符串中的第一个唯一字符

题目描述

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = "leetcode"
返回 0.
s = "loveleetcode"
返回 2.

您可以假定该字符串只包含小写字母。

解题思路及实现

比较简单，通过2次遍历，第一次遍历将每个字符对应出现的次数进行存储，第二次遍历每个字符的出现次数，当出现次数为1，返回该字符的索引即可。

class Solution {
    public int firstUniqChar(String s) {
        char[] arr = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        // 遍历将所有字符的频率输出到Map中
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (map.get(c) == 1)
                return i;
        }
        return -1;
    }
}

5、两个数组的交集 II

题目描述

给定两个数组，编写一个函数来计算它们的交集。

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

解题思路及实现

仍然是通过2次遍历，第一次遍历将nums1[]每个数字对应出现的次数进行存储，第二次遍历nums2[]，然后和之前的结果进行匹配，最终返回结果。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();

        // 遍历数组将所有元素和其数量存入map中
        for (int i = 0; i < nums1.length; i++) {
            int key = nums1[i];
            if (map.containsKey(key)) {
                map.put(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }
        }

        int[] result = new int[nums2.length];
        int pos = 0;
        for (int i = 0; i < nums2.length; i++) {
            int key = nums2[i];
            if (map.containsKey(key) && map.get(key) >= 1) {
                result[pos] = key;
                pos++;
                map.put(key, map.get(key) - 1);
            }
        }

        return Arrays.copyOf(result, pos);
    }
}

6、存在重复元素 II

题目描述

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

输入: nums = [1,2,3,1], k = 3
输出: true
输入: nums = [1,0,1,1], k = 1
输出: true
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

解题思路及实现

题目理解了就好做了，关键是数组内相同的数字最小距离是否不大于k，做一次遍历，每次都将数字作为key，其索引作为value进行存储。

遍历结束前，只要有一个满足要求就可以返回true，否则最终返回false即可。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if (map.containsKey(key)) {
                int oldPos = map.get(key);
                if (i - oldPos <= k) {
                    return true;
                } else {
                    map.put(key, i);
                }
            } else {
                map.put(key, i);
            }
        }
        return false;
    }
}

参考 & 感谢

文章绝大部分内容节选自LeetCode，概述：

• https://leetcode-cn.com/explore/learn/card/hash-table/205/practical-application-hash-map/809/

例题：

• https://leetcode-cn.com/problems/two-sum/
• https://leetcode-cn.com/problems/isomorphic-strings/
• https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/
• https://leetcode-cn.com/problems/first-unique-character-in-a-string/
• https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
• https://leetcode-cn.com/problems/contains-duplicate-ii/

关于我

Hello，我是 却把清梅嗅 ，如果您觉得文章对您有价值，欢迎 ❤️，也欢迎关注我的 博客 或者 GitHub。

如果您觉得文章还差了那么点东西，也请通过关注督促我写出更好的文章——万一哪天我进步了呢？

• 我的Android学习体系
• 关于文章纠错
• 关于知识付费
• 关于《反思》系列