0599.md

title	description	keywords
599. 两个列表的最小索引总和	LeetCode 599. 两个列表的最小索引总和题解，Minimum Index Sum of Two Lists，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 599. 两个列表的最小索引总和 两个列表的最小索引总和 Minimum Index Sum of Two Lists 解题思路 数组 哈希表 字符串

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

🟢 Easy  🔖  数组 哈希表 字符串  🔗 力扣 LeetCode

题目

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all thecommon strings with the least index sum. Return the answer in any order.

Example 1:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

Output: ["Shogun"]

Explanation: The only common string is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]

Output: ["Shogun"]

Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]

Output: ["sad","happy"]

Explanation: There are three common strings:

"happy" with index sum = (0 + 1) = 1.

"sad" with index sum = (1 + 0) = 1.

"good" with index sum = (2 + 2) = 4.

The strings with the least index sum are "sad" and "happy".

Constraints:

• 1 <= list1.length, list2.length <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• list1[i] and list2[i] consist of spaces ' ' and English letters.
• All the strings of list1 are unique.
• All the strings of list2 are unique.
• There is at least a common string between list1 and list2.

题目大意

假设 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 <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
• list1 的所有字符串都是 唯一 的。
• list2 中的所有字符串都是 唯一 的。

解题思路

1. 建立映射：
   • 先遍历 list1，记录每个餐厅的名称和对应的索引，以键值对形式存入哈希表 map1。
2. 查找交集：
   • 遍历 list2，对于每个餐厅名，检查它是否存在于 map1。
   • 如果存在，则计算索引和 sum = i + map1[restaurant]。
3. 更新结果：
   • 维护一个变量 minSum，记录当前最小的索引和。
   • 如果当前餐厅的索引和小于 minSum，则更新 minSum，同时清空结果列表 result 并加入当前餐厅。
   • 如果当前餐厅的索引和等于 minSum，则将餐厅加入结果列表。
4. 返回结果：
   • 遍历结束后，返回结果列表 result。

复杂度分析

• 时间复杂度：O(m + n)，
  • 构建哈希表需要遍历 list1，时间复杂度为 O(m)。
  • 查找交集需要遍历 list2，时间复杂度为 O(n)。
  • 总时间复杂度为 O(m + n)。
• 空间复杂度：O(m)，哈希表存储 list1，需要 O(m) 的额外空间。

代码

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function (list1, list2) {
	// 将 list1 中的餐厅及索引存入哈希表
	const map1 = new Map();
	for (let i = 0; i < list1.length; i++) {
		map1.set(list1[i], i);
	}

	let minSum = Infinity; // 记录最小的索引和
	const result = []; // 存储结果

	// 遍历 list2，计算交集和索引和
	for (let j = 0; j < list2.length; j++) {
		const restaurant = list2[j];
		if (map1.has(restaurant)) {
			const sum = j + map1.get(restaurant); // 索引和
			if (sum < minSum) {
				minSum = sum; // 更新最小索引和
				result.length = 0; // 清空结果
				result.push(restaurant);
			} else if (sum === minSum) {
				result.push(restaurant); // 添加到结果中
			}
		}
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
160	相交链表	[✓]	哈希表 链表 双指针	🟢	🀄️ 🔗