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.

/*暴力的话O（n^2）,可以利用hashtable,用空间来换时间。*/class Solution {public:    vector
     
       findRestaurant(vector
      
       & list1, vector
       
        & list2) {        vector
        
          res;        map
         
           data;        int minval = INT_MAX;        for (int i = 0; i < list1.size(); i++){   // 存入hashtable中            data.insert(pair
          
           (list1[i], i)); } for (int i = 0; i < list2.size(); i++){ if (data.find(list2[i]) != data.end()){ if (data[list2[i]] + i < minval){ minval = data[list2[i]] + i; res.clear(); res.push_back(list2[i]); }else if (data[list2[i]] + i == minval){ res.push_back(list2[i]); } } } return res; }};