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.

本题思路主要是使用 HashMap 进行存储和查询。存储第一个表中的所有字符串,使用字符串作为键,使用下标作为值,这样在对第二个表查找相同字符串的时候就可以对两个下标进行计算和比较。

/*
 * 599. Minimum Index Sum of Two Lists
 * https://leetcode.com/problems/minimum-index-sum-of-two-lists/
 * https://realneo.me/599-minimum-index-sum-of-two-lists/
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class FindRestaurant {
    public static void main(String[] args) {
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};

        FindRestaurant solution = new FindRestaurant();
        System.out.println("result = " + Arrays.toString(solution.findRestaurant(list1, list2)));
    }

    private String[] findRestaurant(String[] list1, String[] list2) {
        List<String> result = new ArrayList<>();

        HashMap<String, Integer> t = new HashMap<>();

        for (int i = 0; i < list1.length; i++)
            t.put(list1[i], i);

        int sum = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (t.containsKey(list2[i])) {
                int temp = i + t.get(list2[i]);
                if (temp < sum) {
                    result.clear();
                    result.add(list2[i]);
                    sum = temp;
                } else if (temp == sum) {
                    result.add(list2[i]);
                    sum = temp;
                }
            }
        }

        return result.toArray(new String[0]);
    }
}