0599. Minimum Index Sum of Two Lists =================================== 题目信息 -------- :题号: 0599 :难度: Easy :主题: 两个字符串列表、公共元素、索引和、并列答案 :原题: `LeetCode 0599 `_ :重点: 字符串必须同时出现于两表、比较两个零基下标之和、返回全部最小并列项、顺序不限 题目重述 -------- 给定两个不含重复字符串的列表 ``list1`` 和 ``list2``。对于同时出现在两个列表中的字符串,计算它在 ``list1`` 和 ``list2`` 中的零基下标之和。 返回所有下标和达到最小值的公共字符串。题目保证至少存在一个公共字符串;若多个字符串并列最小,必须全部返回,结果顺序不限。 自建示例 -------- 只有一个最优公共字符串: .. code-block:: text 输入:list1 = ["A","B","C"],list2 = ["C","A","D"] 输出:["A"] 解释:A 的下标和为 0+1=1,C 的下标和为 2+0=2,因此只返回 A。 多个字符串并列: .. code-block:: text 输入:list1 = ["a","b","c"],list2 = ["b","a","d"] 输出:["a","b"] 解释:a 和 b 的下标和都为 1,二者都达到最小值;输出顺序可以不同。 哈希定位并维护最小下标和 ------------------------ 先记录 ``list1`` 中每个字符串的下标,再扫描 ``list2``。遇到公共字符串时计算两个下标之和;若严格小于当前最优值就清空答案并替换,若相等则追加,这样可以保留全部并列项。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector findRestaurant( std::vector& list1, std::vector& list2) { std::unordered_map position; for (int i = 0; i < static_cast(list1.size()); ++i) { position[list1[i]] = i; } std::vector answer; int best = INT_MAX; for (int i = 0; i < static_cast(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|)``。