哈希

哈希是一种非常重要的算法思想，通过利用某些数据相同的特征对其进行分组，从而大大提高查询时的效率

关键：发现特征，构造函数，避免/减少冲突

例题

两数之和

题目

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

分析

由于题目限定了只存在一个有效答案，即只存在一种组合(x, target - x)，所以考虑使用数+补数的思路进行搜索，即如果一个数x的补数target - x不在数组中，那它一定不在答案中。

考虑到原有的数组中可能存在重复元素，且有可能出现3 + 3 = 6这种组合，所以不能简单粗暴地将原数组转为Java中的HashSet。因此我们选择先新建一个空set，然后遍历原数组，每次拿到一个数时，先查看一下它的补数在不在set中，如果在，算法结束；否则将此数加入set。如果没有数重复，此算法一定可行, 即使存在重复数，如果不是恰好x + x = target的形式，这个数最多有一个就够用了（可能成为其他数的补数），直接加入set去重即可; 如果恰好为x + x = target形式，那么这个数第一次被访问到时会加入set, 再次访问到时它的补数（即自身）已经在set里了，所以找到结果算法结束，因此算法仍然可行。

代码如下

class Solution {
   public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        // 先不初始化map，直接对数做查询操作
        // key存数值，value存索引，假定有重复数，只有当这两个数正好加起来等于target才会被选中，否则无意义，覆盖也没关系，只要有一个还在map中（备选）即可
        // 而当两个相同的数刚好加起来等于target时，他们被选中时一定一个在map中一个在手中，所有不会被覆盖，直接return了
        for (int i = 0; i < nums.length; i++) {
            int fill = target - nums[i];
            if (hashMap.containsKey(fill)) {
                return new int[]{i, hashMap.get(fill)};
            }
            hashMap.put(nums[i], i);
        }
        return new int[]{0, 1};
    }
}

字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

分析

字母异位词的相同特征是拥有完全相同的字符，因此他们按字典序排列自己的字符结果一定一样。所以可以建立一个哈希表，key是字符按字典序排列的字符串，value是key的字母异位词。

代码如下

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 本题关键：找到合适的key
        // 参考解法：将字符串转为字符数组后对数组排序再转为字符串，同一组的字符串相同
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] tmp = str.toCharArray();
            Arrays.sort(tmp); // 字符串按字典序
            String ranked = new String(tmp); 
            if (map.containsKey(ranked)) {
                // 之前已经有同类
                List<String> list = map.get(ranked);
                list.add(str);
            } else {
                // 自己是第一个
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(ranked, list);
            }
        }
        // map构建完毕        
        // 转化为答案
        return new ArrayList<>(map.values());
    }
}

最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

分析

一个连续序列如果是最长的，那么它的开头必然是这个序列组中最小的，即它在数组中不应该有直接前驱。换言之，如果一个数组中的数，它的直接前驱在数组中，那么它一定不是一个最长连续序列的开头，就不需要考虑以它为始的情况了。

那么该如何寻找一个序列的伙伴呢？只需要不断查询当前数的后继是否在数组中即可，若在，则长度加1，继续循环；反之退出，当前长度就是这个序列的极限长度，找出这些极限长度中的最大值即可。

注：本题不能排序，至少我不知道有什么复杂度为O(n)的排序算法，查询采用 Java的 HashSet（数组没有查询的轮子），因为重复数字对于连续序列是无意义的

代码如下

class Solution {
    public int longestConsecutive(int[] nums) {
        // 依然采取HashSet进行去重，不过在数值选择上有所改进
        // 最多使用一个set，多用会增加查询开销
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        int max = 0;
        // 开始查询
        for (int n : set) {
            if (set.contains(n - 1)) {
                // 如果有直接前驱，必然不可能是一个最长的连续序列的开头，直接跳过即可
                continue;
            }
            // 到这里这个数没有直接前驱，可能是开头
            int curLen = 1;
            while (set.contains(n + 1)) {
                curLen++; // 只要直接后继在里面，就说明这个连续序列可以加长 1
                n++;
            }
            max = Math.max(max, curLen);
        }
        return max;
    }
}

复杂度分析

直观上这里存在双重循环，看起来复杂度是O(n)。然而我们从n个数的角度来看，如果一个数有直接前驱，那么它在一开始就被跳过了，只有在作为直接前驱的直接后继时才会被访问一次；**换言之，开头的数只会作为开头被访问一次（不是任何数的直接后继），其他数都只会作为直接后继仅被访问一次。**因此n个数每个都只访问一次，复杂度是O(n)

缺失的第一个正数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

分析

要满足题目的复杂度需求，本题使用原地哈希。因为一个数组可以被看作是一张哈希表，所以把输入的nums看作哈希表，对它进行更新。

因为本题找的是最小的缺失正数，根据鸽巢原理，这个数一定位于**[1, n + 1]**中，问题的关键在于我们怎么记录这个区间中的一个数是否出现过，一个想法是将位于[1, n + 1]中的数放到对应下标的位置，结束后如果某个位置的数和下标(或减1)不一致则说明这个数没有出现，最小的这种数就是答案。因此我们考虑遍历整个数组，将读到的正数放到对应下标位置（如果可以），遍历完后再遍历一遍找答案。

代码如下

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 遍历数组，将遇到的正数放入其值作为下标的位置，如果超出就不动
        // 之后再按顺序遍历一遍数组，若某个位置的下标和元素值不同，则说明他没有出现，第一个就是最小的
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i] - 1 && nums[i] > 0 && nums[i] <= nums.length) {
                int tmp = nums[nums[i] - 1];
                if (nums[i] == tmp) {
                    continue;
                }
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
                i--; // 这个换过来的数可能还没归位，我们保证一下
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] - 1 != i) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

考场就座

题目

在考场里，有 n 个座位排成一行，编号为 0 到 n - 1。

当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

设计一个模拟所述考场的类。

实现 ExamRoom 类：

• ExamRoom(int n) 用座位的数量 n 初始化考场对象。
• int seat() 返回下一个学生将会入座的座位编号。
• void leave(int p) 指定坐在座位 p 的学生将离开教室。保证座位 p 上会有一位学生。

示例 1：

输入：
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
输出：
[null, 0, 9, 4, 2, null, 5]
解释：
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // 返回 0，房间里没有人，学生坐在 0 号座位。
examRoom.seat(); // 返回 9，学生最后坐在 9 号座位。
examRoom.seat(); // 返回 4，学生最后坐在 4 号座位。
examRoom.seat(); // 返回 2，学生最后坐在 2 号座位。
examRoom.leave(4);
examRoom.seat(); // 返回 5，学生最后坐在 5 号座位。

提示：

1. 1 <= n <= 109
2. 保证有学生正坐在座位 p 上。
3. seat 和 leave 最多被调用 104 次。

分析

这题的关键是降低复杂度，超过$O(n)$复杂度的应该都会超时。那怎么降低复杂度？其实还是寻找题目特征，建模，转化问题。这道题的关键在于怎么快速找到距离最近的人最远的座位。距离最近的人可以看成是到两边有人的位置的距离中较短的那一个，换位思考一下就是相邻两个坐了人的位置中间夹着的区间的中点，则区间越长，区间中点的座位距离最近的人越远，相同距离则选择靠前的区间（座位编号小的）。因此我们只需要用一个哈希表维护座位上有人的区间端点即可，seat()就是找到合适的位置坐下，并把该位置作为一个坐了人的端点加入哈希表中，leave(p)就是将区间端点从哈希表中移除。

代码如下：

#include <bits/stdc++.h>
using namespace std;

class ExamRoom {
    // 整理, 题目很不错
public:
    vector<int> hash_set; // 哈希表按顺序记录已经坐了的位置，每个数字代表一个区间端点
    int num;

    ExamRoom(int n) {
        num = n;
    }
    
    int seat() {
        // 特判两种特殊情况
        if (hash_set.empty()) {
            // 没有人左就坐0
            hash_set.push_back(0);
            return 0;        
        }
        int left = -1, right = -1, mmax = 0; 
        if (hash_set[0] != 0) {
            mmax = hash_set[0] * 2;
            left = 0;
            right = 0;
        }
        if (hash_set.back() != num - 1) {
            if (mmax < 2 * (num - 1 - hash_set.back())) {
                mmax = 2 * (num - 1 - hash_set.back());
                left = right = num - 1;
            }
        }
        // 常规情况：
        // 遍历哈希表找到最长的区间，选中点坐下, 存端点时保证升序
        for (int i = 0; i < hash_set.size() - 1; i++) {
            if (mmax / 2 <= (hash_set[i + 1] - hash_set[i]) / 2) {
                if (left != num - 1 && mmax / 2 == (hash_set[i + 1] - hash_set[i]) / 2) {
                    continue; // 防止前面出现比最后一个位置更合适的座位，因为选最小的
                }
                left = hash_set[i], right = hash_set[i + 1];
                mmax = hash_set[i + 1] - hash_set[i];
            }
        }
        // 端点之间的点肯定没有被坐，不然就在哈希表里了
        int pos = (left + right) / 2;
        auto it = upper_bound(hash_set.begin(), hash_set.end(), pos);
        hash_set.insert(it, pos);
        return pos;
    }
    
    void leave(int p) {
        hash_set.erase(remove(hash_set.begin(), hash_set.end(), p));
    }
};

(•‿•)