# LeetCode Easy 599. Minimum Index Sum of Two Lists

tags: leetcode

問題

• Explore
• Problems

アイデア

2つのレストラン名の格納された配列が与えられます．

このときに，最も小さいindexの合計を持つ共通したレストランを探し，それらを配列に入れて返せという問題です．

連想配列が使えそうです．

解法

• 最初に最小のindexの合計min_sumと文字列をkeyとしてindexをvalueとする連想配列を用意します．
• 最初に1つ目の配列の文字列とindexを連想配列に記録します．
• 次に2つ目の配列の文字列を走査していきます．
  • 連想配列に格納されていない場合，次の文字列を見ます．
  • 格納されている場合，そのindexと連想配列のvalueのindexの和がmin_sumよりも小さい時
    • min_sumを更新します．
    • 答えの格納されている配列を消去します．
    • そして，新しく，配列を追加します．
  • min_sumと同じ場合
    • 答えの配列に要素を追加します．

計算量

2つの配列の長さをそれぞれ$N$, $M$とします．

• 時間計算量
  • 配列を走査するので$O(N + M)$
• 空間計算量
  • 配列の中身を記録するので$O(N + M)$

C++

class Solution {
public:
  vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
    map<string, int> common_index;
    int min_sum = INT_MAX;
    vector<string> res;
    for (auto i = 0; i < list1.size(); ++i) {
      common_index[list1[i]] = i;
    }
    
    for (auto i = 0; i < list2.size(); ++i) {
      if (common_index.find(list2[i]) == common_index.end()) {
        continue;
      }
      if (common_index[list2[i]] + i < min_sum) {
        min_sum = common_index[list2[i]] + i;
        res.clear();
        res.push_back(list2[i]);
      } else if (common_index[list2[i]] + i == min_sum) {
        res.push_back(list2[i]);
      }
    }
    return res;
  }
};