Задача: 599. Minimum Index Sum of Two Lists
Сложность: easy

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появляется и в list1, и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

👨‍💻 Алгоритм:

1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string[] FindRestaurant(string[] list1, string[] list2) {
        var map = new Dictionary<int, List<string>>();
        for (int i = 0; i < list1.Length; i++) {
            for (int j = 0; j < list2.Length; j++) {
                if (list1[i] == list2[j]) {
                    if (!map.ContainsKey(i + j)) {
                        map[i + j] = new List<string>();
                    }
                    map[i + j].Add(list1[i]);
                }
            }
        }
        int minIndexSum = int.MaxValue;
        foreach (var key in map.Keys) {
            minIndexSum = Math.Min(minIndexSum, key);
        }
        return map[minIndexSum].ToArray();
    }
}

Ставь 👍 и забирай 📚 Базу знаний