This article was first published on the public account “Monkey Tiangang”

Personal website: liuwyn.github. IO

It’s from LeetCode, problem one.

1. Topic description

Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts.

You can assume that there is only one answer for each type of input. However, you cannot reuse the same elements in this array.

Example:

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

2

Let’s find two numbers a and B that add up to target in a given nums array and return their subscripts I and j in the array.

Specific ideas are as follows:

  1. Define a mapping relation map, in which the data structure is of the form

    , where K ∈[0, nums.length);
    [k],>

  2. Iterate over the given array

    2.1 If nums[k] exists in a map key, the value corresponding to the key and the current k value are the two subscripts we seek.

    2.2 If nums[k] does not exist in the Map key, save

    to the map.
    [k],>

  3. End of loop.

3. Code implementation

Personal energy is limited, currently only Java code algorithm implementation, the future may consider adding other languages implementation, please look forward to oh ~

3.1 Java implementation

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
        for (int i = 0; i < nums.length; i++) {
            // If nums[I] is in map, return nums[I] and I
            if (map.containsKey(nums[i])) {
                return new int[] {map.get(nums[i]), i};
            }
            // If nums[I] is not in map, insert (target-nums[I], I)
            map.put(target-nums[i], i);
        }
        return null; }}Copy the code

4. Algorithm animation

Assume that the given array NUMs is [2, 7, 11, 15] and the target value is equal to 9. According to the algorithm given above, the operation process is shown as follows:

5. The closing

Algorithm is the soul of computer programming, but it is difficult to understand, so the author hopes to reduce the difficulty for beginners to understand in the form of animation.

If you find this article helpful, please scan the following ↓↓↓ public id