Найти наименьшее окно входного массива, которое содержит все элементы массива запроса

Проблема: Для входного массива целых чисел размера n и массива запроса целых чисел размера k найти наименьшее окно входного массива, которое содержит все элементы массива запроса, а также в том же порядке.

Я пробовал подход ниже.

        int[] inputArray = new int[] { 2, 5, 2, 8, 0, 1, 4, 7 };
        int[] queryArray = new int[] { 2, 1, 7 };

Найдет позицию всех элементов массива запроса в inputArray.

public static void SmallestWindow(int[] inputArray, int[] queryArray)
    {
        Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();

        int index = 0;
        foreach (int i in queryArray)
        {
            HashSet<int> hash = new HashSet<int>();
            foreach (int j in inputArray)
            {
                index++;
                if (i == j)
                    hash.Add(index); 
            }
            dict.Add(i, hash);
            index = 0;
        }
      // Need to perform action in above dictionary.??
    }

Я получил следующий словарь

  1. int 2 -> position {1, 3}
  2. int 1 -> position {6}
  3. int 7 -> position {8}

Теперь я хочу выполнить следующий шаг, чтобы найти минимальное окно

  1. Сравните позицию int 2 с позицией int 1. Поскольку (6-3) <(6-1) .. Итак, я сохраню 3, 6 в хэш-карте.

  2. Будет сравнивать положение int 1 и int 7 так же, как указано выше.

Я не могу понять, как я буду сравнивать два последовательных значения словаря. Пожалуйста помоги.

8
задан Pritam Karmakar 19 September 2010 в 05:16
поделиться