Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

A, the title

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.

Given an array of ints and an integer target, return two subscripts whose sum in the array equals target. You can assume that there is an answer to a certain value, and that the same element cannot be used twice.

Second, the answer

Find two numbers that add up to target, and the first response is violence enumeration. If the array length is n, then one loop will do. In Python, you can write code in minutes.

for i in range(len(array)):
    for j in range(len(array)):
        if array[i] + array[j] == target:
            return [i, j]
Copy the code

That’s certainly the right thing to do, but it’s clearly not the best answer. As a rule of thumb, the O(n ^ 2) algorithm is not optimal. In fact, the best solution is to use a map. In this case, we can store the element and its corresponding index in the array into the map. In other words, after storing the subscripts corresponding to all data, we can remove the j loop when traversing, and directly determine whether target-a[j] is in the map. The pseudocode is as follows:

for i in range(len(array)):
    map[array[i]] = i;
    if target - array[i] in map:
        return [i, map[target - array[i]]]
Copy the code

This algorithm looks fine, but if you write your code this way to submit it, it won’t pass. Because there’s a hidden fact that they don’t take into account, they say that you can’t use the same element twice, but they don’t say that there are no duplicate elements in the array. There is a restriction on the use of maps, that is, they cannot have elements with the same key. If there are duplicate elements in the array, the data read later overwrites the previous one. What’s the problem with coverage? There is no way to determine the number of occurrences of elements. The solution is that by using the commutative law of addition and the order in which the elements appear, combined with a map, we can find the answer in just one traverse. It doesn’t matter if there are duplicate elements, because we are checking to see if they exist before updating the map. The pseudocode is as follows:

for i in array.length:
    if target - array[i] in map:
        return i, map[target - array[i]]
    else:
        map.put(array[i], i)
Copy the code