一、题目描述
假设 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[i].length, list2[i].length <= 30list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。list1的所有字符串都是 唯一 的。list2中的所有字符串都是 唯一 的。
二、思路分析
看到这个题，我们会发现这题不难，就是在一个数组里面查找另一个数组的字符串，而且数组的长度也不是很大。
首先从最简单粗暴的方式来说。我们可以使用双层循环，相当于把两个数组的元素做了一个全量连接。时间复杂度比较高，假如使用 n 和 m 分别表示第一个数组和第二个数组的长度，那么这个时间复杂度就是O(n*m)
那么是不是还有更加优雅的解法呢？
这个还真的有，首先我们先分析一下，有哪些数据结构查询比较快——数组和散列表，都可以说是常数级的查询速度。数组只能使用下标访问，而我们要对比的时候字符串，所以这地方我们可以使用散列表存放数组。key就是字符串， value是字符串在数组中的下标。
我们可以先把其中一个数组转化成散列表，然后再遍历另一个数组进行查询对比，这样就把双层循环转化成了两个循环。时间复杂度就被大幅度降低了。
但是吧，这地方还有一些漏洞可以钻的。
当我们第二次遍历数组的时候，如果发现索引已经大于最小索引和的时候，后面的数据就没有遍历的必要了。因为数组下标识从0开始的，所以这里是大于而不是大于等于。
示例代码
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
// 第一个数组转化成散列表
int length = list1.length;
Map<String, Integer> map = new HashMap<>(length);
for (int i = 0; i < length; i++) {
map.put(list1[i], i);
}
// 单个数组长度不超过1000，两个数组索引最大值不超过2000
int minValue = 2000;
List<String> ans = new ArrayList<>();
for (int i = 0; i < list2.length; i++) {
// 如果当前位置的索引已经大于最小值，后面位置上的字符串已经没有检测的意义了
if (i > minValue) {
break;
}
// 如果等于最小值，说明最小结果不止一个，添加到集合中
if (map.containsKey(list2[i]) && i + map.get(list2[i]) == minValue) {
ans.add(list2[i]);
} else if (map.containsKey(list2[i]) && i + map.get(list2[i]) < minValue) {
// 如果出现更小的值，则更新最小值，清空集合重新添加
minValue = i + map.get(list2[i]);
ans.clear();
ans.add(list2[i]);
}
}
return ans.toArray(new String[ans.size()]);
}
}复杂度分析
- 时间复杂度：
O(n + m)，n 表示第一个数组的长度，m表示第二个数组的长度 - 空间复杂度：
O(n)
三、总结
对数据结构要有一定的敏感度，比如那些查询是常量级别的，常见字符串等都可以使用散列表进行存储，查询速度快。很多细节上，还可以看到一些优化空间，可以多思考一下。
