Решаем задачку на leetcode.

Нам даны на вход:

массив чисел nums = [2,7,11,15] и число target = 9

на выходе необходимо вернуть массив индексов, чьи числа дают сумму target (в примере [0,1])

Попытка первого решения:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, num in enumerate(nums):
            if 0 < i + 1 < len(nums):
                if nums[i] + nums[i+1] == target:
                    return [i, i+1]
        return []

Изначально это казалось очевидно и даже проходило первые тесты, но в итоге проверка задачи показала Wrong.

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

Пришлось делать квадратичную сложность.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

И решение сразу прошло проверку.

Решение занимает 1688ms по времени выполнения (что на 31.40% лучше, чем остальные разработчики на Python).

Использует 17.36MB памяти (что на 82.47% лучше, чем остальные)