leetcode-599-easy

Minimum Index Sum of Two Lists

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

Example 1:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.
Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".
Constraints:

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] and list2[i] consist of spaces ' ' and English letters.
All the strings of list1 are unique.
All the strings of list2 are unique.

思路一：用两个 map 存储对应的下标，最后遍历最小的下标。优化，看了一下题解，发现不用两个 map，在遍历第二个数组的时候，此时已经能计算最小值了，直接存储当时的最小值结果就行

public String[] findRestaurant(String[] list1, String[] list2) {
    Map<String, Integer> map1 = new HashMap<>();
    Map<String, Integer> map2 = new HashMap<>();

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

    int min = Integer.MAX_VALUE;
    for (int i = 0; i < list2.length; i++) {
        if (map1.containsKey(list2[i])) {
            int val = map1.get(list2[i]) + i;
            min = Math.min(val, min);
            map2.put(list2[i], val);
        }
    }

    List<String> result = new ArrayList<>();
    for (Map.Entry<String, Integer> e : map2.entrySet()) {
        if (e.getValue() == min) {
            result.add(e.getKey());
        }
    }

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

原文地址：http://www.cnblogs.com/iyiluo/p/16829652.html