python-3.x 给定一个目标,从列表中找出目标的和

omhiaaxx  于 2023-01-03  发布在  Python
关注(0)|答案(2)|浏览(124)

给定一个数字列表和一个目标值,我将找到与目标值匹配的两个数字的和,并从数组中返回和的索引。
我试过:

nums = [2,5,5,11]
target = 10

def nums_sum_target(nums, target):
    for i in range(len(nums)):
        for j in range(len(nums)):
            if j == len(nums) - 1:
                target_sum = nums[i]
            else:
                print(j+1, "inner loop 2")
                target_sum = nums[i] + nums[j+1]
                
            if target_sum == target:
                print([nums[i], nums[j+1]])
                return [i, j+1]

我期望:[1,2]
我有:[1,1]

pinkon5k

pinkon5k1#

解决方案应与以下示例类似

def nums_sum_target(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]

顺便说一下,还有另一种方法涉及使用哈希表来存储数组的元素及其索引,这允许更有效的搜索,并可以在O(n)时间内解决问题。

def nums_sum_target(nums, target):
    hashmap = {}
    for i in range(len(nums)):
        if nums[i] not in hashmap:
            hashmap[target-nums[i]] = i 
        else:
            return hashmap[nums[i]], i
mtb9vblg

mtb9vblg2#

如果数字是排序的,你可以利用这一点,从两端开始迭代,如下所示:

def find_sum(numbers, target):
    assert numbers  # Should have at least 1 number
    left = 0
    right = len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return (left, right)
        elif total < target:
            left += 1
        else:
            right -= 1
    raise LookupError(f"Sum {target} not found")

测试功能:

numbers = [2, 3, 4, 5]
target = 6

indices = find_sum(numbers, target)
print(indices)  # prints (0, 2)

不需要字典或其他任何东西,只需要列表和目标,这是一种非常有效的方法,最坏的情况是O(n)

相关问题