Python两次求和-蛮力法 [英] Python Two Sum - Brute Force Approach

问题描述

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

I'm new to Python and have just started to try out LeetCode to build my chops. On this classic question my code misses a test case.

问题如下:

给出一个整数数组，返回两个数字的索引，以便它们加起来成为一个特定的目标.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

示例:

给出数字= [2，7，11，15]，目标= 9，

Given nums = [2, 7, 11, 15], target = 9,

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

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

我错过了目标编号为6的测试用例[3,2,4]，它应该返回索引[1,2]，但是在目标编号为测试用例[1,5,7]的情况下6(当然会返回索引[0,1])，因此在while循环中似乎出现了问题，但是我不太确定是什么.

I miss on test case [3,2,4] with the target number of 6, which should return the indices of [1,2], but hit on test case [1,5,7] with the target number of 6 (which of course returns indices [0,1]), so it appears that something is wrong in my while loop, but I'm not quite sure what.

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分配错误吗?

Output returns null on test case [3,2,4] with target 6, so indices 1 and 2 aren't even being summarized, could I be assigning y wrong?

推荐答案

方法有所不同.我们将根据需要构建一个值字典，该字典由我们要查找的值作为关键字.如果我们寻找一个值，则在该值首次出现时会对其进行索引.一旦找到满足问题的值，就可以完成.时间也是O(N)

Bit different approach. We will build a dictionary of values as we need them, which is keyed by the values we are looking for.If we look for a value we track the index of that value when it first appears. As soon as you find the values that satisfy the problem you are done. The time on this is also 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)

这篇关于Python两次求和-蛮力法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！