LC 599. 两个列表的最小索引总和

题目描述

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

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

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

示例 1:

1
2
3
4
5
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]

输出: ["Shogun"]

解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:
1
2
3
4
5
输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]

输出: ["Shogun"]

解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

提示:

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

哈希表

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

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

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

  • 如果 $list2[i]$ 不在哈希表中，跳过：
  • 如果 $list2[i]$ 在哈希表中：
    • 索引之和等于 $min$，将 $list2[i]$ 加入 $ans$；
    • 索引之和小于 $min$，更新 $min$，清空 $ans$，将 $list2[i]$ 加入 $ans$；
    • 索引之和大于 $min$，跳过。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 + m)$
  • 空间复杂度：$O(n)$

答疑

评论区有位同学提出了一个挺有意思的疑问，或许是部分同学的共同疑问，这里集中答疑一下。

Q0: for 循环里的 ans.clear() 这个函数也是 $O(n)$ 复杂度吧，为什么合起来还是 $O(n)$ ?

A0: 在 ArrayList 源码中的 clear 实现会为了消除容器对对象的强引用，遍历容器内的内容并置空来帮助 GC。

但不代表这会导致复杂度上界变成 $n^2$。

不会导致复杂度退化的核心原因是：由于 clear 导致的循环计算量总共必然不会超过 $n$。因为最多只有 $n$ 个元素在 ans 里面，且同一元素不会被删除多次（即每个元素对 clear 的贡献不会超过 $1$）。

如果有同学还是觉得不好理解，可以考虑一种极端情况：clear 操作共发生 $n$ 次，但发生 $n$ 次的前提条件是每次 ans 中只有 $1$ 位元素，此时由 clear 操作带来的额外计算量为最大值 $n$。

因此这里的 clear 操作对复杂度影响是「累加」，而不是「累乘」，即复杂度仍为 $O(n)$，而不是 $O(n^2)$。


Q1: 判断 $list[i]$ 是否在哈希中的操作，复杂度是多少？

A1: 在 Java 的 HashMap 实现中，当键值对中的键数据类型为 String 时，会先计算一次（之后使用缓存）该字符串的 HashCode，计算 HashCode 的过程需要遍历字符串，因此该操作是与字符串长度相关的（对于本题字符串长度不超过 $30$），然后根据 HashCode「近似」$O(1)$ 定位到哈希桶位置并进行插入/更新。

因此在 Java 中，该操作与「当前的字符串长度」相关，而与「当前容器所包含元素多少」无关。

最后

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

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

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

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