﻿ 599. Minimum Index Sum of Two Lists 列表下标最小和

### 599. 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.

``public class Solution {``    public string[] FindRestaurant(string[] list1, string[] list2) {``        ``        List<Pair> listPair1 = new List<Pair>();``        ``        for(int i = 0;i<list1.Length;i++)``        {``            Pair pair =new Pair(list1[i], i);``            listPair1.Add(pair);``        }``        ``        ``        List<string> lowestMatchList = new List<string>();``        int lowestMatchIndex = Int32.MaxValue;``        for(int i = 0;i<list2.Length;i++)``        {``            foreach(Pair pair in listPair1)``            {``                string restaurant = list2[i];``                if(restaurant== pair.Restaurant)``                {``                    int sum = i + pair.Index;``                    ``                    if(sum == lowestMatchIndex)``                    {``                        ``                        lowestMatchList.Add(restaurant);``                    }``                    else if(sum < lowestMatchIndex)``                    {``                        lowestMatchIndex = sum;``                        if(lowestMatchList.Count > 0)``                        {``                            lowestMatchList.Remove(lowestMatchList[0]);``                        }``                        lowestMatchList.Add(restaurant);``                    }``                }``            }``        }``        return lowestMatchList.ToArray();``        ``    }``    ``    public class Pair``    {``        public string Restaurant {get;set;}``        public int Index {get;set;}``        public Pair(string restaurant, int index)``        {``            Restaurant = restaurant;``            Index = index;``        }``    }``}``