# LeetCode 599: 两个列表的最小索引总和 Minimum Index Sum of Two Lists

### 题目：

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.

输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]

输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]

1. 两个列表的长度范围都在 [1, 1000] 内。
2. 两个列表中的字符串的长度将在 [1，30] 的范围内。
3. 下标从 0 开始，到列表的长度减 1。
4. 两个列表都没有重复的元素。

Note:

1. The length of both lists will be in the range of [1, 1000].
2. The length of strings in both lists will be in the range of [1, 30].
3. The index is starting from 0 to the list length minus 1.
4. No duplicates in both lists.

### 哈希表解题：

Java：

class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> map = new HashMap<>();//建立哈希映射
for (int i = 0; i < list1.length; i++)//初次遍历将一个数组建立映射关系
map.put(list1[i], i);
List<String> res = new ArrayList<>();//待返回的目标数组
int sum = Integer.MAX_VALUE;//sum为当前满足条件的最小索引和
for (int i = 0; i < list2.length; i++) {//第二次遍历查找目标元素
if (map.containsKey(list2[i])) {
int tmp = i + map.get(list2[i]);//当前索引和
if (tmp < sum) {//如果当前索引和更小
res.clear();//清除目标数组
sum = tmp;// 刷新最小索引和
} else if (tmp == sum)//如果索引和相等
}
}
return res.toArray(new String[res.size()]);//转成 string 数组
}
}

Python：

class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
hash_map = dict()# 建立哈希映射
for i, s in enumerate(list1):# 初次遍历将一个数组建立映射关系
hash_map[s] = i
min_sum = 2001# 当前满足条件的最小索引和
res = list()# 待返回的目标数组
for i, s in enumerate(list2):# 第二次枚举遍历查找目标元素
if s in hash_map:
tmp = i+hash_map[s]# 当前索引和
if tmp < min_sum:# 如果当前索引和更小
res.clear()# 清除目标数组
res.append(s)# 添加该元素
min_sum = tmp# 刷新最小索引和
elif tmp == min_sum:# 如果索引和相等
res.append(s)# 只添加元素
return res

### 操作索引解题：

!--链接：https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/solution/liang-ge-lie-biao-de-zui-xiao-suo-yin-zong-he-by-l/--

Java：

class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
List<String> res = new ArrayList<>();
for (int sum = 0; sum < list1.length + list2.length - 1; sum++) {
for (int i = 0; i <= sum; i++) {
if (i < list1.length && sum - i < list2.length && list1[i].equals(list2[sum - i]))
}
if (res.size() > 0) break;//一旦找到最小索引和序列直接结束遍历，因为sum是递增的，之后得到的索引和一定更大
}
return res.toArray(new String[res.size()]);
}
}

Python

class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
res = list()
list1_size, list2_size = len(list1), len(list2)
for min_sum in range(list1_size+list2_size-1):
for i in range(min_sum+1):
if i < list1_size and min_sum-i < list2_size and list1[i] == list2[min_sum-i]:
res.append(list1[i])
if len(res) > 0:# 一旦找到最小索引和序列直接结束遍历，因为sum是递增的，之后得到的索引和一定更大
break
return res

|
9月前
Leetcode Minimum Depth of Binary Tree （面试题推荐）

34 0
|
11月前
|

LeetCode刷题---Two Sum（一）
LeetCode刷题---Two Sum（一）
|
3天前
|

LeetCode初级算法题：寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149：直线上最多的点数 Java详解
LeetCode初级算法题：寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149：直线上最多的点数 Java详解
10 0
|
7天前
|

【Leetcode刷题Python】852. 山脉数组的峰顶索引

11 0
|
2月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
36 1
|
2月前
|

LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
35 4
|
3月前
|

Leetcode 给定一个数组，给定一个数字。返回数组中可以相加得到指定数字的两个索引
Leetcode 给定一个数组，给定一个数字。返回数组中可以相加得到指定数字的两个索引
32 0
|
10月前
|

【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
31 0
|
3月前
|

【python刷题】LeetCode 2057E 值相等的最小索引（5种简单高效的解法）
【python刷题】LeetCode 2057E 值相等的最小索引（5种简单高效的解法）
37 0
|
9月前
Leetcode 4. Median of Two Sorted Arrays

21 0