LeetCode刷题坚持每一天！今天是摸鱼的一天！题目LeetCode 599. 两个列表的最小索引总和.

题目

假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个，则输出所有答案并且不考虑顺序。你可以假设答案总是存在。

示例

示例 1:

1
2
3

输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

1
2
3

输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

题解

这个题目让我纠结了很久，主要是“最少的索引和”这个字眼让我十分疑惑，翻了翻评论区得到解释 —— 两列表的下标和（看来还是我自己的理解能力不够哇/_ \），那么这样就说得通可以开始解题了。

整个题目意思其实就是让我们在最小下标和的情况下输出两个列表中同样的元素项目，也就是说我们既然能够输出下标和为 1 的答案，就不要输出下标和为 2 的答案，尽管下标和为 2 的元素比下标和为 1 的元素多。

那么我们就针对list1建立一个哈希表，每个元素内容作为 first，对应的 second 为list1中这个元素的下标；而后我们可以开始循环遍历list2，当list2中的元素内容在哈希表中能找到，那么就计算list1此元素的下标与此元素在list2中对应的下标的和，然后对比 vector<string> ans 中的元素所指向的下标和，如果当前元素的下标和小于ans中元素的下标和，那么就直接清空ans并添加当前元素，但如果两元素的下标相等，那么就将其直接添加进数组ans中。

只需要这样，我们就能确定ans中的元素一定是我们需要的那些个。

那么开始写代码吧！

代码

//执行 100ms 超越23%   内存 35.8 MB 超越 78%
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        map<string,int> list1_;//哈希表
        for(int i=0;i<list1.size();i++)//遍历输入哈希表
            list1_[list1[i]]=i;
        vector<string> ans;
        for(int i=0;i<list2.size();i++)
        {
            if(list1_.find(list2[i])!=list1_.end())
            {
                list1_[list2[i]]+=i;  //计算下标和
                if(ans.size()==0)  //当ans中没有元素时直接添加
                    ans.push_back(list2[i]);
                else if(list1_[ans[0]]>list1_[list2[i]])  //当ans中的元素在map中的下标和大于list2[i]时则清空替换
                    ans.clear(),ans.push_back(list2[i]);
                else if(list1_[ans[0]]==list1_[list2[i]]) //当ans中的元素在map中的下标和等于list2[i]时则添加进ans
                    ans.push_back(list2[i]);
            }
        }
        return ans;
    }
};