Вы делаете много работы, которая не нужна. Часто хорошей идеей является создание объекта заранее, как у вас, но в этом случае это не победа. Вам нужно только выполнить итерацию по массиву один раз, и есть лишь несколько фактов, которые необходимо отслеживать между итерациями:
prevPositions - Объект для отслеживания самого последнего индекса каждого элемента, видимого на данный момент. distance - Наименьшее расстояние между парами. position1, position2 - Индексы пары с наименьшим на данный момент расстоянием.
(Технически distance всегда можно рассчитать, вычитая position1 из position2, но мы сэкономим небольшую работу, сохранив ее отдельно.)
В каждой итерации вам необходимо:
- Проверьте, видели ли вы текущий элемент раньше.
- Если да, проверьте, меньше ли расстояние между текущим элементом и его предыдущим вхождением, чем наименьшее расстояние до настоящего времени.
- Если да, сохраните новое наименьшее расстояние в
distance и индексы текущего и предыдущего вхождений в position1 и position2.
- Сохранить индекс текущего элемента в
prevPositions.
После того, как вы перебрали каждый элемент один раз, position1, position2 и distance будут содержать индексы ближайшей пары и расстояние между ними.
Это O ( n ). Вы можете увидеть, как это выглядит в JavaScript, в следующем фрагменте кода.
function closestMatchingPair(array) {
if (array.length < 2) {
throw new Error('Input must have at least two items');
}
// An object to track the most recent positions of the items we've seen so far
const prevPositions = {};
// Variables to track the smallest distance so far and corresponding indexes
let distance, position1, position2;
for (let index = 0; index < array.length; index++) {
const currentItem = array[index];
if (currentItem in prevPositions) {
// We've seen this item before; check if the distance from the previous
// instance is less than the smallest distance we've seen so far
const currentDistance = index - prevPositions[currentItem];
if (!distance || currentDistance < distance) {
// New smallest distance; update our variables
distance = currentDistance;
position1 = prevPositions[currentItem];
position2 = index;
if (currentDistance === 1) {
// Can't do any better than 1; no reason to continue
break;
}
}
}
prevPositions[currentItem] = index; // Save item's index
}
return { pairFound: !!distance, position1, position2, distance };
}
test([1]);
test([1,2]);
test([1,2,1]);
test([1,2,1,3,2,2]);
function test(input) {
console.log('input:', input);
try {
console.log('output:', closestMatchingPair(input));
} catch (e) {
console.error(e.message);
}
}
.as-console-wrapper{min-height:100%}
Примечание: Этот код использует простой объект для prevPositions. Это прекрасно работает, если ваш входной массив содержит только цифры или только строки. Однако, если ваш вклад был, например, [1, '1'] эти два значения считаются равными, поскольку числовые ключи приводятся к строкам при использовании в качестве имен свойств объекта. (Технически это немного сложнее, чем это, но вы поняли идею.) Если вы хотите, чтобы это работало со смешанным массивом, вам нужно будет использовать Map вместо объекта.