Welcome to learn algorithms with Mr. Xia. In this respect, MY own foundation is very weak, so the methods and ideas to solve problems will also be very “white”, which can be understood without any foundation.

Attention to the public number can be exchanged and join the wechat group, the group has a regular series of articles to share oh!

The problem

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

Nested loop solution

The first loop gets the current and remaining values, and then the nested loop checks to see if the remaining values are in the array.

function twoSum(nums, target) {
  for(let i = 0; i<nums.length; i++) {const current = nums[i]; // Get the current value
    const remain = target - current; // Get the remaining value
    
    for(let j = 1; j<nums.length; j++) {if(nums[j] === remain) {
        return[i, j]; }}}}Copy the code

The time is order n^2.

The length of nums is n, the total number of iterations of the nested loop is n times (n-1), and n-1 is no different from n as n approaches infinity, ignore

Space complexity is O(1).

Add temporary variables such as current, remain, I, j, do not increase with nums length, so is constant O(1)

Nested loops are the least efficient, and the chances of being sent away during an interview are high.

HashTable 2

The idea is to use a HashTable to hold each value and its location.

The first loop constructs a HashTable with keys for the elements of the NUMS array and values for the subscripts of the elements

If the index of the remaining value is not equal to the index of the current value, and the remaining value is also in the HashTable, the current value and the index of the remaining value are read directly from the HashTable.

function twoSum(nums, target) {
  const hashTable = {};
  // the first loop
  for(let i = 0; i<nums.length; i++) { hashTable[nums[i]] = i; }// The second loop
  for(let i = 0; i<nums.length; i++) {const current = nums[i];
    const remain = target - current;
    if(map[remain] ! = =undefined&& map[remain] ! == i) {return[i, map[remain]]; }}}Copy the code

Time complexity is O(2n) = O(n)

It loops twice, theoretically 2 times n time, but as n goes to infinity, the difference between n and 2n is negligible, so it’s O(n).

The space complexity is order n.

Add HashTable, size is nums length n, so space complexity is O(n)

The algorithm uses the O(1) time complexity of HashTable to cleverly reduce the nested loop, the algorithm efficiency is greatly improved!

The general answer is basically no problem at this point, but there is another solution based on HashTable that loops once to solve the problem.

Let’s use HashTable

Loop through the numS array, get the current value and the remaining value, determine whether the remaining value is in the HashTable, if so, directly return the remaining value and the current value position. If not, insert the remaining values into the HashTable and continue the loop.

Q: Why is the position of the remaining value returned first instead of the current value?

A: Because the position of the current value is fixed, the current value is not in the HashTable, but the remaining value may have been inserted into the HashTable in the previous loop and is old, so return first.

function twoSum(nums, target) {
  const hashTable = {};
  
  for(let i = 0; i<nums.length; i++) {const current = nums[i];
    const remain = target - remain;
    if(hashTable[remain] ! = =undefined) { // Why not determine the position? Because the position of the current value is not inserted into the HashTable at all, the index cannot be repeated
      return [hashTable[remain], i];
    }
    hashTable[current] = i; // Insert the current value into the HashTable, and the next time around it will be "old"}}Copy the code

Time complexity O(n)

Authentic O(N), solve the problem once in a loop

Space complexity O(n)

Added HashTable, which increases in size as NUMs increases

At the end

The sum of the two numbers is the first problem of Leetcode, which is also a relatively simple problem. Readers who are afraid of the algorithm can receive the heart in their stomach, and learn the algorithm with The teacher Xia! Readers with questions can scan the qr code above and communicate with me.