Leetcode Two Sum вопрос. Временная сложность моего кода O (n ^ 2). Как я могу сделать это проще

Question

class Solution:
    def twoSum(self, nums, target):
        i = 0
        while i <= (len(nums) - 1):   
            j = i + 1 
            for c, y  in enumerate(nums):
                if y == (target - nums[i]) and i != c:
                    return [i, c]
            i += 1

Чем я должен заменить while l oop на?

Answer 1

Не дам вам точный код. Но может дать вам представление об алгоритме. Используйте HashMap. Сохраняйте разницу target и текущий номер в качестве ключа, а позицию в качестве значения.

Если вы обнаружите разницу в hashmap, то значением этой записи и текущей будет ваш ответ.

Al go:

for each number
    int diff = target - number
    if(map.contains(diff)) 
        return map.get(value), current index
    else 
        store the diff, index