I. Title Description:

That’s Leetcode number 1: the sum of two numbers

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:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Example 3:

Input: nums = [3,3], target = 6Copy the code

Ii. Analysis of Ideas:

1. Enumerate violence

The first thing to think about is enumerating all the elements of an array, doing a two-level for loop, looking for the subscripts of the target elements x and y that x + y = target. Complexity analysis: Time complexity: O(n^2) where n is the number of elements in the array. We did two for loops, so the time is n^2. Space complexity: O(1), no extra space is opened in the array itself, so the space complexity is 1.

2. Hash Map

Solution 2 is optimized on the basis of solution 1 to speed up the time of finding the target element. The characteristic of hash table is that the time complexity of searching elements is O(1), so you can use hash Map structure to quickly find the target elements in the array. We can create a Map that iterates over each element of the array and uses the Map to see if target-x exists. If x does not exist, we insert x into the Map and return the target element’s index if it matches. Time complexity: O(n), where n is the number of elements in the array. Do a layer traverse for each element x, and then we can look O(1) for target-x. Space complexity: O(n), where n is the number of elements in the array. Mainly the overhead of the hash table.

Iii. AC Code:

Violent solution code:

var twoSum = function(nums, target) {
    let len = nums.length;
    let arrs = [];
    
    if(!(nums instanceof Array)){
        return 'it is not Array';
    }
    
    if(len < 2) {
        return 'it is length < 2'
    }else{
        for(let i = 0;i<len-1;i++) {
            for(let j=0;j<len;j++) {
                if(i == j) {
                    continue
                }else{
                    if(nums[i] +nums[j] === target){
                        arrs.push(i,j);
                        return arrs;
                    }
                }
            }
        }
    }
};
Copy the code

Hash map solution code:

var twoSum = function (nums, target) { let map = new Map(); for (let i = 0; i < nums.length; i++) { let valIndex = map.get(target - nums[i]); if (valIndex ! == undefined) { return [valIndex, i]; } else { map.set(nums[i], i); }}};Copy the code

Iv. Summary:

On the first day, I chose to start with the sum of the simplest two numbers, both to encourage myself that solving algorithm problems is not difficult, and to learn one of the most important ways to improve code efficiency: trading “cheap” space complexity for “expensive” time complexity. The optimized hash map solution adopts the method of space for time. Tomorrow continue refueling duck ~~

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign