哈希表总结与题型扩展：外星字典序与连续数组

Java:

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            int w1_len = w1.length();
            String w2 = words[i + 1];
            int w2_len = w2.length();
            for (int j = 0; j < Math.max(w1_len, w2_len); j++) {
                int idx_w1 = j > w1_len ? -1 : map.get(w1.charAt(j));
                int idx_w2 = j > w2_len ? -1 : map.get(w2.charAt(j));
                if (idx_w1 > idx_w2) return false;
                if (idx_w1 < idx_w2) break;
            }
        }
        return true;
    }
}

题目二：连续数组

难度：中等

描述： 给定一个二进制数组 nums，找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例：

• 输入：nums = [0,1]
• 输出：2
• 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

分析： 这道题如果将 0 视为 -1，问题就转化为了寻找和为 0 的最长子数组。为什么这么转化？因为当 -1 和 1 的数量相同时，它们的累加和必然为 0。

这里需要用到前缀和的概念。如果我们记录前缀和，当发现当前的前缀和在之前出现过时，说明这两个位置之间的子数组元素之和为 0。

配合哈希表的使用，我们可以快速记录 {前缀和：下标} 的关系。由于可能存在从索引 0 开始就满足条件的情况，我们需要在哈希表中预置一个节点 {0: -1}，以规避边界问题。

具体逻辑如下：

1. 遍历数组，遇到 1 则前缀和 +1，遇到 0 则前缀和 -1。
2. 检查当前前缀和是否在哈希表中存在。
3. 如果存在，计算当前索引与首次出现该前缀和的索引之差，更新最大长度。
4. 如果不存在，将当前前缀和及其索引存入哈希表。

代码实现：

Python：

class Solution:
    def findMaxLength(self, nums):
        d = {0: -1}
        ret = pre_sum = 0
        for i, num in enumerate(nums):
            pre_sum += 1 if num == 1 else -1
            pre_index = d.get(pre_sum, i)
            if pre_index == i:
                d[pre_sum] = i
            else:
                ret = max(ret, i - pre_index)
        return ret

Java：

class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int pre_sum = 0;
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            pre_sum += nums[i] == 1 ? 1 : -1;
            int pre_index = map.getOrDefault(pre_sum, i);
            if (pre_index == i) {
                map.put(pre_sum, i);
            } else {
                ret = Math.max(ret, i - pre_index);
            }
        }
        return ret;
    }
}

小结

525 号题目（连续数组）是一道综合题，结合了前缀和思维与哈希表的应用。而像剑指 Offer II 035 最小时间差这类题目，作为哈希表的延伸练习，大家可以尝试自行解决。

哈希表章节至此告一段落。希望这些实战案例能帮你建立起更扎实的解题直觉。