0599. Minimum Index Sum of Two Lists

题目信息

题号:

0599

难度:

Easy

主题:

两个字符串列表、公共元素、索引和、并列答案

原题:

LeetCode 0599

重点:

字符串必须同时出现于两表、比较两个零基下标之和、返回全部最小并列项、顺序不限

题目重述

给定两个不含重复字符串的列表 list1 和 list2。对于同时出现在两个列表中的字符串,计算它在 list1 和 list2 中的零基下标之和。

返回所有下标和达到最小值的公共字符串。题目保证至少存在一个公共字符串;若多个字符串并列最小,必须全部返回,结果顺序不限。

自建示例

只有一个最优公共字符串:

输入:list1 = ["A","B","C"],list2 = ["C","A","D"]
输出:["A"]
解释:A 的下标和为 0+1=1,C 的下标和为 2+0=2,因此只返回 A。

多个字符串并列:

输入:list1 = ["a","b","c"],list2 = ["b","a","d"]
输出:["a","b"]
解释:a 和 b 的下标和都为 1,二者都达到最小值;输出顺序可以不同。

哈希定位并维护最小下标和

先记录 list1 中每个字符串的下标,再扫描 list2。遇到公共字符串时计算两个下标之和;若严格小于当前最优值就清空答案并替换,若相等则追加,这样可以保留全部并列项。

C++ 实现

class Solution {
public:
    std::vector<std::string> findRestaurant(
        std::vector<std::string>& list1,
        std::vector<std::string>& list2) {
        std::unordered_map<std::string, int> position;
        for (int i = 0; i < static_cast<int>(list1.size()); ++i) {
            position[list1[i]] = i;
        }

        std::vector<std::string> answer;
        int best = INT_MAX;
        for (int i = 0; i < static_cast<int>(list2.size()); ++i) {
            auto it = position.find(list2[i]);
            if (it == position.end()) continue;
            int sum = it->second + i;
            if (sum < best) {
                best = sum;
                answer.clear();
                answer.push_back(list2[i]);
            } else if (sum == best) {
                answer.push_back(list2[i]);
            }
        }
        return answer;
    }
};

代码分析

哈希表把 list1 的查找从线性扫描降为平均常数时间;list2 按顺序扫描时,答案只在发现更小或相等的下标和时更新,既不会遗漏并列项,也不会保留旧的较差项。时间复杂度为平均 O(|list1| + |list2|),额外空间复杂度为 O(|list1|)。