Имеет ли смысл начинать второй цикл с начала при поиске пары чисел в массиве

Что проверяют

Видите ли вы лишнюю работу во вложенном цикле и понимаете ли, что сдвиг начального индекса не меняет асимптотику. Обычно следом просят решение быстрее квадратичного и спрашивают, чем за него платим.

Как отвечать

Для симметричного условия вроде «сумма равна target» начинать внутренний цикл с нуля смысла нет:

• повторы: пара (i, j) проверяется дважды, второй раз как (j, i);
• пара с самим собой: при j === i элемент складывается сам с собой, и для [3] с target = 6 найдётся несуществующая пара. Такой код приходится латать проверкой i !== j;
• правильный вариант: for (let j = i + 1; j < arr.length; j++). Сравнений становится n(n-1)/2 вместо n², примерно вдвое меньше, но это всё ещё O(n²).

С нуля начинать имеет смысл, когда условие несимметрично и порядок в паре важен: например, ищете все пары, где a[i] делит a[j]. Тогда пропускаете только j === i.

Дальше предложите решения лучше:

• хеш за один проход: для каждого числа проверяете, есть ли в Set дополнение target - x, и только потом добавляете x. Время O(n), память O(n). Порядок «сначала проверка, потом добавление» и защищает от пары элемента с самим собой. Нужны индексы, берите Map с числом в ключе и индексом в значении;
• сортировка и два указателя: O(n log n) по времени без дополнительной структуры. Помните, что sort() без компаратора сравнивает строки, нужен (a, b) => a - b, а чтобы не мутировать входной массив, есть toSorted() (Node.js 20+).

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

Где спотыкаются

Говорят, что O(n²) получается «из-за двух проходов по массиву». Два последовательных прохода это O(n), квадрат даёт вложенность.

Считают вариант с j = i + 1 улучшением сложности. Работы вдвое меньше, но на миллионе элементов это всё ещё сотни миллиардов сравнений.

Используют обычный объект вместо Set или Map. Ключи объекта приводятся к строкам, 1 и '1' становятся одним ключом, а унаследованные ключи вроде constructor дают ложные совпадения.