LeetCode_哈希表_简单_599.两个列表的最小索引总和

喜欢ヅ旅行 2023-10-07 20:01 61阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。你可以假设答案总是存在。

**示例 1：**  
输入: list1 = \[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”\]，list2 = \[“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”\]  
输出: \[“Shogun”\]  
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

**示例 2：**  
输入:list1 = \[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”\]，list2 = \[“KFC”, “Shogun”, “Burger King”\]  
输出: \[“Shogun”\]  
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

**提示：**  
1 <= list1.length, list2.length <= 1000  
1 <= list1\[i\].length, list2\[i\].length <= 30  
list1\[i\] 和 list2\[i\] 由空格 ’ ’ 和英文字母组成。  
list1 的所有字符串都是唯一的。  
list2 中的所有字符串都是唯一的。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-index-sum-of-two-lists

## 2.思路 ##

（1）哈希表  
① 使用 hashMap 记录 list1 中每个餐厅名称以及对应的索引，并用变量 minIndexSum 为最小索引总和，初始值为 Integer.MAX\_VALUE；  
② 遍历 list2，如果当前餐厅 list2\[i\] 存在于 hashMap 中，则说明该餐厅是两人共同喜爱的餐厅，然后将其索引和与 minIndexSum 进行比较。如果该索引和比 minIndexSum 小，则更新 minIndexSum 为该索引和，然后清空 res，并将该餐厅加入 res；如果该索引和等于 minIndexSum ，则直接将该餐厅加入结果中。

## 3.代码实现（Java） ##

//思路1————哈希表
    class Solution {
        
        public String[] findRestaurant(String[] list1, String[] list2) {
        
            List<String> res = new ArrayList<>();
            Map<String, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < list1.length; i++) {
        
                hashMap.put(list1[i], i);
            }
            // minIndexSum 为最小索引总和，初始值为 Integer.MAX_VALUE;
            int minIndexSum = Integer.MAX_VALUE;
            for (int i = 0; i < list2.length; i++) {
        
                String curName= list2[i];
                if (hashMap.containsKey(curName)) {
        
                    int j = hashMap.get(curName);
                    if (i + j < minIndexSum) {
        
    	                //更新 minIndexSum
                        minIndexSum = i + j;
                        //清空 res
                        res.clear();
                        res.add(curName);
                    } else if (i + j == minIndexSum) {
        
                        res.add(curName);
                    }
                }
            }
            return res.toArray(new String[res.size()]);
        }
    }