Given a target, find the sum of the target from a list-CodePudding

Given a list of numbers and a target value, I am to find the sum of two numbers that matches the target and returns the indexes of the sum from the array.

I have tried:

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]

I expected: [1,2]

I had: [1,1]

CodePudding user response：

The solution should be similar to the following example

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]

By the way there is another approach involves using a hash table to store the elements of the array and their indices, which allows for more efficient searches and can solve the problem in O(n) time.

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

CodePudding user response：

If the numbers are sorted, you can take advantage of that and just iterate from both ends like so:

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

Testing the function:

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

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

No need for a dictionary or anything else, just the list and the target, and this is an extremely efficient way, with a worse case of O(n).