> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/overlapping/minimum-index-sum-of-two-lists.md).

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

## 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)