599. 两个列表的最小索引总和 : 哈希表模拟题

题目描述

这是 LeetCode 上的 599. 两个列表的最小索引总和 ，难度为 简单。

Tag : 「哈希表」、「模拟」

假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。

示例 1:

输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。
复制代码

示例 2:

输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
复制代码

提示:

• 1 <= list1.length, list2.length <= 10001<=list1.length,list2.length<=1000
• 1 <= list1[i].length, list2[i].length <= 301<=list1[i].length,list2[i].length<=30
• list1[i]list1[i] 和 list2[i]list2[i] 由空格 ' ' 和英文字母组成。
• list1list1 的所有字符串都是 唯一 的。
• list2list2 中的所有字符串都是 唯一 的。

哈希表

为了快速判断某个字符串是否在另外一个数组中出现，我们可以先使用「哈希表」对 list1 中的字符串进行处理，以 (list1[i]: i)(list1[i]:i) 键值对形式进行存储。

然后遍历 list2，判断每个 list2[i]list2[i] 是否在哈希表中出现过，同时维护一个当前的 最小索引总和minmin，以及 用于存储能够取得最小索引总和的字符串数组ansans。

假设当前遍历到的元素是 list2[i]list2[i]，根据「list2[i]list2[i] 是否在哈希表中出现」以及「当前索引和与 minmin 的大小关系」分情况讨论：

• 如果 list2[i]list2[i] 不在哈希表中，跳过：
• 如果list2[i]list2[i]在哈希表中：

• 索引之和等于 minmin，将 list2[i]list2[i] 加入 ansans；
• 索引之和小于 minmin，更新 minmin，清空 ansans，将 list2[i]list2[i] 加入 ansans；
• 索引自核大于 minmin，跳过。

代码：

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int n = list1.length, m = list2.length;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(list1[i], i);
        List<String> ans = new ArrayList<>();
        int min = 3000;
        for (int i = 0; i < m; i++) {
            String s = list2[i];
            if (!map.containsKey(s)) continue;
            if (i + map.get(s) < min) {
                ans.clear();
                min = i + map.get(s);
                ans.add(s);
            } else if (i + map.get(s) == min) {
                ans.add(s);
            }
        }
        return ans.toArray(new String[ans.size()]);
    }
}
复制代码

• 时间复杂度：O(n)O(n)
• 空间复杂度：O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.599 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。