哈希映射用法及算法例题

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

用法

哈希映射 是用于存储 (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学习体系
• 关于文章纠错
• 关于知识付费
• 关于《反思》系列

最后

以上就是忧心水池为你收集整理的哈希映射用法及算法例题的全部内容，希望文章能够帮你解决哈希映射用法及算法例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。