LeetCode 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. 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).

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.

---

给定两个字符串数组，要求在两个数组中都出现的字符串在各自数组中的下标之和最小的字符串，如果有多个这样的字符串下标之和一样小，则都输出。 简单题，对两个数组，建立两个hash表，存储字符串对应下标的关系。然后遍历其中一个hash表，在如果该字符串在另一个hash表中存在，则更新下标之和。 代码如下： [cpp] class Solution { public: vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) { unordered_map<string, int> hash1, hash2; for (int i = 0; i < list1.size(); ++i)hash1[list1[i]] = i; for (int i = 0; i < list2.size(); ++i)hash2[list2[i]] = i; int global_min_sum = INT_MAX; vector<string> ans; for (int i = 0; i < list1.size(); ++i) { if (hash2.find(list1[i]) != hash2.end()) { if (i + hash2[list1[i]] < global_min_sum) { global_min_sum = i + hash2[list1[i]]; ans.clear(); ans.push_back(list1[i]); } else if (i + hash2[list1[i]] == global_min_sum) { ans.push_back(list1[i]); } } } return ans; } }; [/cpp] 本代码提交AC，用时115MS。]]>