Minimum Index Sum of Two Lists

https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/

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 theircommon interestwith theleast 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.

Thoughts

想找出相同的string并且加起来index最小。找是否用共同元素想到hash set/table, 又因为要记录index，于是用map.

Code

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }

        int min = Integer.MAX_VALUE;
        List<String> set = new ArrayList<>();
        for (int i = 0; i < list2.length; i++) {
            if (map.containsKey(list2[i])) {
                if (i + map.get(list2[i]) < min) {
                    set.clear();
                    set.add(list2[i]);
                    min = i + map.get(list2[i]);
                } else if (i + map.get(list2[i]) == min) {
                    set.add(list2[i]);
                }
            }
        }

        String[] result = new String[set.size()];
        for (int i = 0; i < set.size(); i++) {
            result[i] = set.get(i);
        }
        return result;
    }
}

Analysis

做题耗时: 13min

时间复杂度O(mn), 空间O(n)