Python Two Sum - Подход грубой силы

Question

Я новичок в Python и только начал пробовать LeetCode для создания своих котлет. По этому классическому вопросу мой код пропускает контрольный пример.

Проблема заключается в следующем:

Учитывая массив целых чисел, вернуть индексы двух чисел так, чтобы они суммировались с определенной целью.

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

Пример:

Учитывая числа = [2, 7, 11, 15], цель = 9,

Потому что nums [0] + nums [1] = 2 + 7 = 9, возврат [0, 1].

Я скучаю по контрольному примеру [3,2,4] с целевым номером 6, который должен возвращать индексы [1,2], но попал по контрольному примеру [1,5,7] с целевым номером из 6 (что, конечно, возвращает индексы [0,1]), поэтому кажется, что что-то не так в моем цикле while, но я не совсем уверен, что.

class Solution:
    def twoSum(self, nums, target):
        x = 0
        y = len(nums) - 1
        while x < y:
            if nums[x] + nums[y] == target:
                return (x, y)
            if nums[x] + nums[y] < target:
                x += 1
            else:
                y -= 1
        self.x = x
        self.y = y
        self.array = array       
        return None

test_case = Solution()    
array = [1, 5, 7]
print(test_case.twoSum(array, 6))

Выходные данные возвращают ноль в тестовом примере [3,2,4] с целью 6, поэтому индексы 1 и 2 даже не суммируются, могу ли я назначить y неправильно?

Answer 1

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

class Solution:
    def twoSum(self, nums, target):
        for i, a in enumerate(nums, start=0):
            for j, b in enumerate(nums[i+1:], start=0):
                if a+b==target:
                    return [i, j+i+1]

test_case = Solution()
array = [3, 2, 4]
print(test_case.twoSum(array, 6))

array = [1, 5, 7]
print(test_case.twoSum(array, 6))

array = [2, 7, 11, 15]
print(test_case.twoSum(array, 9))

Вывод:

[1, 2]
[0, 1]
[0, 1]

Answer 2

import itertools

class Solution:
    def twoSum(self, nums, target):
        subsets = []
        for L in range(0, len(nums)+1):
            for subset in itertools.combinations(nums, L):
                if len(subset)!=0:
                    subsets.append(subset)
        print(subsets) #returns all the posible combinations as tuples, note not permutations!
        #sums all the tuples
        sums = [sum(tup) for tup in subsets]
        indexes = []
        #Checks sum of all the posible combinations
        if target in sums:
            i = sums.index(target)
            matching_combination = subsets[i] #gets the option
            for number in matching_combination:
                indexes.append(nums.index(number))
            return indexes
        else:
            return None


test_case = Solution()    
array = [1,2,3]
print(test_case.twoSum(array, 4))

Я пробовал ваш пример для собственного обучения. Я доволен тем, что нашел. Я использовал itertools, чтобы составить для меня всю комбинацию чисел. Затем я использовал манипулирование списком для суммирования всех возможных комбинаций чисел в вашем входном массиве, затем я просто проверяю одним выстрелом, находится ли цель в массиве сумм или нет. Если нет, верните None, в противном случае верните индексы. Обратите внимание, что при таком подходе будут возвращены также все три индекса, если они соответствуют цели. Извините, что так долго :)

Answer 3

class Solution:
    def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            ls=[]
            l2=[]
            for i in nums:
                ls.append(target-i)

            for i in range(len(ls)):
                if ls[i] in nums  :
                    if i!= nums.index(ls[i]):
                        l2.append([i,nums.index(ls[i])])            
            return l2[0]


x= Solution()
x.twoSum([-1,-2,-3,-4,-5],-8)

выход

[2, 4]

Answer 4

Немного другой подход. Мы создадим словарь значений по мере необходимости, который определяется значениями, которые мы ищем. Если мы ищем значение, мы отслеживаем индекс этого значения при его первом появлении. Как только вы найдете значения, которые удовлетворяют задаче, вы сделали. Время на это также O (N)

class Solution:
    def twoSum(self, nums, target):
        look_for = {}
        for n,x in enumerate(nums):
            try:
                return look_for[x], n
            except KeyError:
                look_for.setdefault(target - x,n)

test_case = Solution()
array = [1, 5, 7]
array2 = [3,2,4]
given_nums=[2,7,11,15]
print(test_case.twoSum(array, 6))
print(test_case.twoSum(array2, 6))
print(test_case.twoSum(given_nums,9))

выход:

(0, 1)
(1, 2)
(0, 1)