This time, I decided to go back to the first problem I had done on LeetCode and look at the commit record. It was two years ago.

1. The sum of two numbers

First, look at the problem

Given an integer array nums and an integer 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, the same element in an array cannot be used twice.

You can return the answers in any order.

Example 1:

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

Output: [0, 1]

Because nums[0] + nums[1] == 9, return [0, 1]

Example 2:

Enter: nums = [3,2,4], target = 6

Output: [1, 2]

Tip:


  • 2 < = n u m s . l e n g t h < = 1 0 3 2 <= nums.length <= 10^3

  • – 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9

  • – 1 0 9 < = t a r g e t < = 1 0 9 -10^9 <= target <= 10^9
  • There can only be one valid answer

Second, organize your thoughts

I vaguely remember the first time I did it I went through it by brute force twice and then I ran out of time. After I got it this time, I thought about it and found that the intuitive solution was still traversal, but instead of traversal twice, I used indexOf instead of traversal and pruned by condition, passing the test case once.

The first step:

Confirm input and output:

Input: an array; Output: an array.

The second step

What do you do with the input to get the output?

Since you need to traverse at least once to find pairs of elements, the difficulty of optimization is to reduce the number of traversals.

The initial notation is to optimize by pruning:

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    let res=[]
    for(let i=0; i<nums.length; i++){// It doesn't matter whether it's greater than or less than, just to cut the computation in half
        if(target-nums[i]<=nums[i]){
            let idx=nums.indexOf(target-nums[i])
            // As indexOf is used, it is possible to find yourself
            // So we must add subscript judgment
            if(i! =idx&&idx>=0){ res=[i,idx]}
        }
    }
    return res
};
Copy the code

After pruning, the computation speed is improved considerably, at least without running out of time. However, I vaguely felt that this was still not the best way, so I referred to the solution, and suddenly realized that Map was the best choice.

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    let map = new Map(a)for(let i=0; i<nums.length; i++){let rest = target-nums[i]
        if(map.has(rest){
            return [map.get(rest),i]
        }else{
            map.set(nums[i],i)
        }
    }
};
Copy the code

Use Map to record and search subscripts, not only do not worry about finding itself, but also reduce memory consumption, more importantly, the code ideas at a glance.

Third, summary

Summation

Solution: pruning method; Hash table

As the first problem of leetcode, it feels different to do it after two years. Time flies, seize the present.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign