Python二和蛮力方法

Question

我是Python新手，刚刚开始尝试使用LeetCode来构建我的排骨。在这个经典问题上，我的代码遗漏了一个测试用例。

问题如下：

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

您可以假设每个输入都有一个精确的解决方案，并且您可以不使用相同的元素两次。

例子：

给定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]上，输出返回null，因此索引1和2甚至没有被汇总，我是否会将y赋值错误？

Answer 1

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 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)

Answer 3

强力解决方案是在列表上双嵌套一个循环，其中内部循环只查看大于外部循环当前所在索引的索引。

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]