Твое O(n^2) решение правильное, просто медленное. На собесах в яндексе/гугле важна именно коммуникация процесса мышления, а не то что ты сразу выдашь идеальный код.

Алгоритм ответа такой:

1. Подтверди что понял задачу, переспроси граничные случаи (пустой массив? дубликаты? несколько пар?)
2. Назови наивное решение и его сложность
3. Скажи что можно оптимизировать - предложи хэшмапу
4. Напиши код, проговаривая каждую строку
5. Сам прогони на примерах из условия

Эта задача это буквально первый номер на LeetCode (Two Sum). Прорешай там хотя бы 50 medium задач до собеса.

Вообще-то O(n log n) тоже принимается если сортировать и использовать два указателя. Хэшмап не единственное решение, просто самое очевидное. Иногда интервьюер специально спрашивает про альтернативы после того как ты дал O(n).

Два указателя:

def twoSum(nums, target):
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    l, r = 0, len(indexed) - 1
    while l < r:
        s = indexed[l][1] + indexed[r][1]
        if s == target:
            return [indexed[l][0], indexed[r][0]]
        elif s < target:
            l += 1
        else:
            r -= 1

Но если просто хотят быстрое решение - хэшмап проще объяснять.

Честно говоря задача настолько затаскана что любой нормальный интервьюер понимает - ты её мог вызубрить. Поэтому они потом дают вариации: а что если массив отсортирован, а что если нужно три числа, а что если числа с плавающей точкой. Хэшмапу выучи, но готовься объяснять почему именно она, а не просто рецитировать решение.

Решение с хэшмапой хорошее, но ВНИМАНИЕ на детали реализации!

Если не учесть что в массиве могут быть дубли, можно получить баг. Например nums = [3, 3], target = 6. Твой словарь перезапишет первую тройку второй, и вернешь [1, 1] вместо [0, 1].

В решении выше этот кейс обработан правильно (сначала проверка, потом запись), но на собесе именно об этом и надо сказать сразу - показывает что думаешь об edge cases.