1. The sum of two numbers

This is LeetCode number 1: the sum of two numbers

Given an integer array nums and an integer target, find the two integers in the array whose sum is the target value and return their array indices. You can assume that there is only one answer for each input. However, you cannot use the same element in an array twice. You can return the answers in any order.

Example 1:

Input: nums = [2.7.11.15], target = 9Output:0.1] explanation: because nums[0] + nums[1] = =9To return to the [0.1].Copy the code

Example 2:

Input: nums = [3.2.4], target = 6Output:1.2]
Copy the code

Example 3:

Input: nums = [3.3], target = 6Output:0.1]
Copy the code

1. Violence

It is easiest to enumerate all the elements of an array and run a two-level for loop to find the subscripts of the target elements x + y = target. Complexity analysis: Time complexity: O(n^2), where n is the number of elements in the array. I’ve done two for loops, so the time complexity is n^2. Space complexity: O(1), there is no extra space for the array itself, so the space complexity is 1.

var twoSum = function(nums, target) {
    let len = nums.length;
    let arrs = [];
    
    if(! (numsinstanceof 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);
                        returnarrs; }}}}}};Copy the code

2. Hash Map

Solution 2 is optimized on the basis of solution 1 to speed up the search time of target elements. The characteristic of hash table is that the time complexity is O(1) when looking for elements, so the hash Map structure can be used to quickly find the target elements in the array. We can create a Map, iterate over each element of the array, and look through the Map to see if target-x exists. If x does not exist, insert x into the Map, and return the index of the target element if it matches. Complexity analysis: Time complexity: O(n), where n is the number of elements in the array. We do one level of traversal for each element x, and then we can find target-x in order (1). Space complexity: O(n), where n is the number of elements in the array. Mainly the cost of the hash table.

var twoSum = function (nums, target) {
  let map = new Map(a);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);
     // The first is a key and the second is a value}}};Copy the code

  • Think of NUMS1 as a kinsman

  • Think of target as a match condition

  • Use a dictionary to set up a dating agency that stores the numbers and subscripts of your partners

  • Ideas:

    • Create a new dictionary as a dating agency
    • numsIn the value, one by one to introduce the object, there is no appropriate on the first registration, there is a suitable hand success
var twoSum = function (nums, target) {
    const map = new Map(a);for (let i = 0; i < nums.length; i++) {
        const n = nums[i];
        const n2 =target -n;
        if(map.has(n2)){
            // map.get is to get the value of the key in the map and the array is 1 => 0 2 => 1 is to the right of index
            return [map.get(n2),i];
        }else {
            // The first is a key and the second is a value
            map.set(n,i)
        }
    }
};
// Time complexity O(n)
// Space complexity O(n)

// Space for time
Copy the code

conclusion

On the first day, I chose to start with the sum of the simplest two numbers, one is to encourage myself to brush algorithm problems is not difficult, the other is to learn one of the important means to improve the efficiency of the code: with “cheap” space complexity for “expensive” time complexity. The optimized hash map solution adopts the method of space for time. Continue refueling duck tomorrow ~~

❤️ Thank you all

If you think this content is very helpful to you: like support, let more people can also see this content (collection does not like, is playing rogue – -) follow the public number to NPY front secret, we learn together progress. If you like it, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)

The sum of two numbers