主要思路还是一个一个找。一开始写了一个简单的双重循环的版本但是数据规模大的时候超时了，所以优化了一下算法：设一个门限值，只要当前找到的字符串索引之和小于门限就更新这个门限，同时list1在门限值之后的值都不查找了（因为肯定比当前结果大了）。
注意门限最大值应该设成两倍的最大list长度，结果也可能不唯一所以每次替换的时候要clear盛放结果的容器。
class Solution { public: vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) { int l1 = list1.size(); int l2 = list2.size(); if (l1 < l2) { swap(list1, list2); swap(l1, l2); } vector<string>a; int threshold = 20000; int i = 0; string mark; while ((i<threshold+1) && (i<l1)) { if (find(list2.begin(), list2.end(), list1[i]) != list2.end()) { string temp = list1[i]; int dis = distance(list2.begin(), find(list2.begin(), list2.end(), list1[i])); if ((i + dis) < threshold) { mark = list1[i]; threshold = i + dis; a.clear(); a.push_back(mark); } else if (i + dis == threshold) a.push_back(list1[i]); } i++; } return (a); } };其实当时也想了一个只要遍历两遍list的算法但是没想到可以用map这个容器。map1以餐馆名字为键值，索引和为另一个值。一开始默认所有餐馆都带双倍惩罚值（list1和list2的长度之和，类似我的门限值），出现在一个list里则减掉它（再加上餐馆的索引值）。遍历完之后再新建一个以索引值之和为键值的map，输出其begin位置的值即可，因为map内部本身就是默认按照键值的大小排序的。
优化：我们可以假设惩罚值是0，那么得到的索引都是负数，只要索引值越小就越好。
class Solution { public: vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) { int punish = l1.size() + l2.size(); // use n as a punishment for missing in either list; map<string, int> m; for (int i = 0; i < l1.size(); i++) m[l1[i]] += i - punish; for (int j = 0; j < l2.size(); j++) m[l2[j]] += j - punish; map<int, vector<string>> rank; for (auto p : m) rank[p.second].push_back(p.first); return rank.begin()->second; } }; 注意auto这个用法，默认p就是m里的数据类型，不需要定义。
