Author : dyq666, zhihu.com/people/dyq666

This topic mainly introduces two methods of hash table and pointer to solve this kind of problem, from the sum of two numbers to the sum of three numbers, and then from the problem of the sum of four numbers, how to construct a universal Code (can solve the sum of N numbers). The main content of this article is to get a preliminary understanding of the two common methods of array summation through the 001 problem.

001-Two Sum

Given an integer array and a target value, find the two numbers in the array whose sum is the target value. You can assume that each input corresponds to only one answer, and the same elements cannot be reused.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9, it returns [0, 1]

1. Cycle of Violence

O(n^2)

The only thing to note is that the same element cannot be reused

nums_len = len(nums)

for i in range(0, nums_len):
    for j in range(i + 1, nums_len):
        if nums[i] + nums[j] == target:
            return [i, j]

2. Hash

(1) O(n)

(2) Considering what we do in the violent cycle, we first pick a value a, and then see whether other values ​​in the array can be added to the value a to equal the target, or whether there is a value in the array equal to the target value Subtract the value a.

(3) Another way of thinking is that we store all the traversed values, and every time we traverse to a new value b, we can find whether the target value minus the value b is in the value we stored. Based on the characteristics of the hash table, the time complexity of the lookup is O(1), and the total time complexity becomes O(n) for a for loop.

Back to this question:

(1) Since the corresponding index needs to be returned, it is necessary to use HashMap (dict in python), key stores the value in the array, value stores the index in the array, traverse the array, and store the traversed value in the dict, if the target The value minus the current value in the dict proves that the target value is found.

(2) Another thing to note is that if you want to return the values ​​in ascending order, the previous value must be stored in the dict (because it was traversed before).

seen_dict = {} 

for i, num in enumerate(nums):

    search = target-num
    if search in seen_dict:
        return [seen_dict[search], i]
    else:
        seen_dict[num] = i

3. Double pointer

(1) O(nlogn)-mainly the effect of fast rowing

(2) In an ordered array, the leftmost must be the minimum value, and the rightmost must be the maximum value. We can add the minimum and maximum values ​​to compare with the target value. If the sum of the two numbers is greater than the target value, we make the maximum value smaller (that is, read the second maximum value), on the contrary, if it is less than, let The minimum value is larger (read the second minimum value). In this way, we ensure that the target value can be found in one loop, but the array must be in order.

Back to the topic:

(1) Since the index needs to be returned, we must store two arrays, one is unordered (used to find the real index), and the other is ordered (used to find the value that matches the topic).

(2) The two pointers left and right respectively point to the first element and the last element in the array (minimum value and maximum value)

(3) The end condition of the loop is that the left pointer is greater than or equal to the right pointer (the left pointer cannot be larger than the right pointer, and an element can only be used once)

(4) Then judge the relationship between the left value + right value and the target value. We have discussed the situation of greater than and less than above.

(5) When equals, since we need to get the index of the lvalue and rvalue in the original array, we need to consider the following issues. From the question, it is known that each target has only one answer, which means that if the target is 6, the situation of [2, 2, 4] will not appear, but the situation of [3, 3] will appear, that is, when the two are the same There will be duplicate elements only if the value is satisfied. So we first get the index corresponding to the left value through index. If the left value and the right value are the same, we get the index of the next value. If they are different, we directly get the index related to the right value.

raw_nums = nums

nums = sorted(nums)

left, right = 0, len(nums)-1   

while left <right:
    v_left, v_right = nums[left], nums[right]

    two_sum = v_left + v_right

    if two_sum> target:
        right -= 1
    elif two_sum <target:
        left += 1
    else: # found
        left_index = raw_nums.index(v_left)
        # If the values ​​are the same, find the index of the next value
        right_index = raw_nums.index(v_right, left + 1) if v_right == v_left else raw_nums.index(v_right)
        return [left_index, right_index]

summary

Through the two number sum problem, we have a preliminary understanding of the array sum problem. The next article will extend the application of these two methods in the sum of three numbers.