Leetcode刷题java之599. 两个列表的最小索引总和

秒速五厘米 2023-06-06 12:10 53阅读 0赞

执行结果：

通过

显示详情

执行用时 :8 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗 :38.7 MB, 在所有 Java 提交中击败了97.85%的用户

题目：

假设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, 1000\]内。  
两个列表中的字符串的长度将在\[1，30\]的范围内。  
下标从0开始，到列表的长度减1。  
两个列表都没有重复的元素。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

创建一个hashmap用来存储值和相应索引，为什么要用它呢，因为它里面有containsKey方法，直接可以判断有没有，然后，输出要求是最小索引，所以得存储一下索引进行计算。最后，遍历第二个数组，如果有更小索引和则清空，重新加入。如果等于，则直接再加入一个。

代码：

class Solution {
        public String[] findRestaurant(String[] list1, String[] list2) {
            HashMap<String,Integer> map=new HashMap();
            for(int i=0;i<list1.length;i++)
            {
                map.put(list1[i],i);
            }
            List<String> result=new ArrayList<>();
            int sum;
            int min_sum=Integer.MAX_VALUE;
            for(int j=0;j<list2.length&&j<=min_sum;j++)
            {
                if(map.containsKey(list2[j]))
                {
                    sum=j+map.get(list2[j]);
                    if(sum<min_sum)
                    {
                        result.clear();
                        result.add(list2[j]);
                        min_sum=sum;
                    }else if(sum==min_sum)
                    {
                        result.add(list2[j]);
                    }
                }
            }
            //列表变字符串数组的重要方法
            return result.toArray(new String[result.size()]);
        }
    }