Python两数之和 - 暴力解法

Question

我刚开始尝试使用LeetCode来提高我的Python编程技能。在这个经典问题中，我的代码无法通过一个测试用例。

问题描述如下：

给定一个整数数组，返回两个数字的索引，使它们相加等于特定目标。

您可以假设每个输入都只有一种解决方案，并且您不可以重复使用相同的元素。

示例：

给定nums = [2, 7, 11, 15]，target = 9，

因为nums[0] + nums[1] = 2 + 7 = 9， 返回[0, 1]。

我无法通过目标数字为6的测试用例[3,2,4]，应该返回[1,2]的索引，但是通过目标数字为6的测试用例[1,5,7]（当然返回[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))

当目标为6时，在测试用例[3,2,4]上输出为空，因此索引1和2甚至没有被汇总，是否我错误地赋值了y？

- csheroe

---

你的解决方案只适用于已排序的列表。 - Michael Butscher

另外，请确保x和y不相等。 - Ahad Sheriff

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]

- tarheel

---

你的解决方案非常干净。我需要帮助理解通过添加j+i+1发生的登录。为什么不只是i+1？我很好奇。 - Anjayluh

Answer 2

有一种不同的方法。我们会在需要时构建一个值的字典，这个字典以我们正在查找的值作为键。如果我们查找一个值，我们会跟踪该值第一次出现时的索引。一旦找到满足问题的值，就完成了。此方法的时间复杂度也是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)

- d_kennetz

---

我明白了，我觉得一开始应该像这样使用enumerate来处理它。更简单和更有效率。 - csheroe

这是一个不断学习的过程，但我们不想重复造轮子:P。很高兴能帮忙。 - d_kennetz

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]

- sahasrara62

Answer 4

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，否则返回索引。请注意，如果它们加起来等于目标，此方法也将返回所有三个索引。抱歉花费了这么长时间 :)

- Arka Mallick

Answer 5

这个更全面、连贯、高效，即使代码行更短。

nums = [6, 7, 11, 15, 3, 6, 5, 3,99,5,4,7,2]
target = 27
n = 0

for i in range(len(nums)):
    
    n+=1
    if n == len(nums):
      n == len(nums)
      
    else:
        if nums[i]+nums[n] == target:
          # to find the target position 
          print([nums.index(nums[i]),nums.index(nums[n])])
          # to get the actual numbers to add print([nums[i],nums[n]])

- Yyuv Ali

---

我认为这可能无法在所有测试用例中运行，a=[3,3] t=6，a[9,9] t=18。 - Shivam Suchak