问题

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。
示例 1:
输入:
\(["Shogun", "Tapioca Express", "Burger King", "KFC"]\)
\(["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]\)
输出: \(["Shogun"]\)
解释: 他们唯一共同喜爱的餐厅是\("Shogun"\)。

示例 2:

输入:
\(["Shogun", "Tapioca Express", "Burger King", "KFC"]\)
\(["KFC", "Shogun", "Burger King"]\)
输出: \(["Shogun"]\)
解释: 他们共同喜爱且具有最小索引和的餐厅是\("Shogun"\)，它有最小的索引和1(0+1)。
提示:

1. 两个列表的长度范围都在 \([1, 1000]\)内。
2. 两个列表中的字符串的长度将在\([1，30]\)的范围内。
3. 下标从\(0\)开始，到列表的长度减\(1\)。
4. 两个列表都没有重复的元素。

解法1

直接看上去就是两个数组求并集的一个延伸，那么直接使用双层循环+特殊退出条件即可完成。时间复杂度\(O(m*n)\)，其中\(m、n\)为两个数组的长度。

代码1

java

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        // 最小索引和
        int minIndex = Integer.MAX_VALUE;
        List<String> result = new LinkedList<>();
        // 第一层循环，可以依靠minIndex来缩短部分循环
        for(int i = 0;i < list1.length && i <= minIndex; i++) {
            // 第二层循环，依靠i与minIndex可以缩短部分循环
            for(int j = 0;j < list2.length && i + j <= minIndex; j++) {
                // 如果两个元素相等，才进入后面的判断
                if (list1[i].equals(list2[j])) {
                    // 如果i+j<minIndex，说明找到了更小的索引和，需要重置result，并且 缩小minIndex
                    if (i + j < minIndex) {
                        minIndex = i + j;
                        result.clear();
                        result.add(list1[i]);
                    } else if (i + j == minIndex) {
                        result.add(list1[i]);
                    }
                }
            }
        }
        return result.toArray(new String[0]);
    }
}

解法2

解法1时间复杂度较高，能不能通过另外的手段降低呢？同时发现提示中有个数组中没有重复元素的前提，考虑java中的HashMap（插入、查询的时间复杂度可以认为是\(O(1)\)的）来保存其中一个列表的字符串与索引值。另一个数组再次遍历一下查找HashMap中是否存在相同的关系就可以了。两个循环非嵌套，所以可以认为时间复杂度为\(O(m+n)\)的。
另外，为了减少空间复杂度与降低HashMap的hash冲突，考虑对两个数组中较小的那个放入HashMap中。同时，更极端的情况下需要考虑HashMap的rehash对时间复杂度与空间复杂度的影响。

代码2

java

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int l1 = list1.length;
        int l2 = list2.length;
        
        //找到规模更小的数组进行hash化
        if (l1 > l2) {
            return findRestaurant(list2, list1);
        }
        //极端情况下需要考虑rehash
        Map<String, Integer> map = new HashMap<>(l1);
        for(int i = 0;i < l1; i++) {
            map.put(list1[i],i);
        }
        int minIndex = Integer.MAX_VALUE;
        List<String> result = new LinkedList<>();
        
        //遍历第二个数组，这里可以用j<=minIndex来提前跳出循环，因为大于的必然不在结果中
        for(int j = 0;j < l2 && j <= minIndex; j++) {
            Integer index = map.get(list2[j]);
            if (index != null) {
                if (index + j < minIndex) {
                    minIndex = index + j;
                    result.clear();
                    result.add(list2[j]);
                } else if (index + j == minIndex){
                    result.add(list2[j]);
                }
                
            }
        }
        return result.toArray(new String[0]);
    }
}