［抄题］：
Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.
You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.
Example 1:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
Example 2:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
两次求和的长度有可能相等，都是最大，需要直接往结果里添加
［思维问题］：
以为要存两个hashset。但其实直接取，判断是否为空即可，能少存一次
［一句话思路］：
存一次，取一次
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 有新的最小值之和时，记得实时更新
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
存一次，取一次
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
res.toArray(new String[res.size()]) list变成数组，里面再放字符串，字符串还要指定大小。转了3次。
直接指定string的尺寸：用方括号
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
//ini: hashmap, linkedlist
Map<String, Integer> map = new HashMap<>();
List<String> res = new LinkedList<>();
int minSum = Integer.MAX_VALUE;
//put list1 into hashmap
for (int i = 0; i < list1.length; i++) {
map.put(list1[i], i);
}
//get from list2
for (int i = 0; i < list2.length; i++) {
Integer j = map.get(list2[i]);
if (j != null && i + j <= minSum) {
if (i + j < minSum) {
res.clear();
minSum = i + j;
}
res.add(list2[i]);
}
}
//return, change form
return res.toArray(new String[res.size()]);
}
}