• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

directory

  1. Bubble sort
  2. The sum of two Numbers([],Number) => []

Bubble sort

Compares the size of two record keys, and if the keys are in reverse order, the records are swapped

function bubbleSort(arr){
    for(let i = 1; i < arr.length; i++){for(letj = i; j >0; j--){if(arr[j] < arr[j-1]){
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]]; }}}return arr;
}
var arr = [3.4.2.1];
bubbleSort(arr); // [1, 2, 3, 4]
Copy the code

The sum of two numbers([],Number) => []

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 = 9Output:0.1Because nums[0] + nums[1] = =9To return to the [0.1]
Copy the code

Example 2:

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

Example 3:

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

You can iterate over all pairs of numbers, double-loop over whether the current value and another current value are equal to the target value, and return the result if they are equal.

1) Traversal mode([],Number) => []

You start with the 0th one and you add it to the next one, and if you don’t, you start with the first one and you add it to the last one. Optimization: (less traversal) The outer for traversal condition can be changed to: I < nums.length-1

/ * * *@param {number[]} nums
* @param {number} target
* @return {number[]}* /
var twoSum = function(nums, target) {
 for (let i = 0; i < nums.length-1; i++) { // Optimization: (less traversal) 'outer for traversal condition' can be changed to: 'I < nums.length-1'
  console.log('i:',i)
  for (let j = i + 1; j < nums.length; j++) {
   console.log('j:',j);
   if (nums[i] + nums[j] === target) {
    return[i,j]; }}}};var nums = [200.70.2]; 
var target = 290;
twoSum(nums, target);

Copy the code

Execution process:

I: 0 j: 1 2 I: 1 j: 2 I: 2 j: not executedCopy the code
  • Add the 0th to the second and the third, return
  • Add the first and the second, return
  • Number two is the last number, and the inner loop is over
var nums = [200.70.2]; 
var target = 270;
twoSum(nums, target);
Copy the code

2) Traversal mode + indexOf

var twoSum = function(nums, target) { for(let i = 0; i < nums.length; i++) { var index = nums.indexOf(target-nums[i]); if(index ! == -1 && index ! == i) { return [i,index] } } }; Var nums = [4] 2; var target = 7; twoSum(nums, target); / / [1, 2]Copy the code

3) Traversal is stored by Map

var twoSum = function(nums, target) {
  const map = new Map(a);for (let i = 0; i < nums.length; i++) {
   const diff = target - nums[i];
   if (map.has(diff)) {
    return[map.get(diff), i]; } map.set(nums[i], i); }};var nums = [2.3.4]; 
var target = 7;
twoSum(nums, target); / / [1, 2]
Copy the code

4) Dual-pointer mode

Use two Pointers to search, improve search efficiency

var twoSum = function(nums, target) {
    if(! nums.length)return [];
    let num = nums.slice(0);
    nums.sort((x,y) = > x-y);
    let l = 0,r = nums.length-1;
    while(l < r){
        if(nums[l] + nums[r] === target) break;
        else if(nums[l] + nums[r] < target){
            l++;
        }else{
            r--;
        }
    }
    l = num.indexOf(nums[l]);
    r = num.indexOf(nums[r]) === l ? num.indexOf(nums[r],l+1) : num.indexOf(nums[r])
    return [l,r];
};
var nums = [2.3.4]; 
var target = 7;
twoSum(nums, target);

Copy the code

5) Lookup table method

  • While traversing, some information is recorded to eliminate a layer of loop, which is the idea of space for time

  • The need to record the traversal of the value and its corresponding subscript, you can use the lookup table to achieve

  • Two common implementations of lookup tables

    • Hash table
    • Balanced binary tree search
function twoSum(arr, target) { var temp = [] let len = arr.length for (let i = 0; i < len; i++) { let dif = target - arr[i] if (temp[dif] ! == undefined) { return [temp[dif], i] } temp[arr[i]] = i } }; let arr = [2, 3, 5, 9] console.log(twoSum(arr, 7)) // [0, 2]Copy the code
  • throughlet dif = target - arr[i]Respectively to obtainThe targetwithThe difference between the elements currently traversedIf thisdifferenceAs a hash tableThe index, can access valid elements, then the current traversaliwithtemp[dif], is to findThe index

[2, 3, 5, 9] The target value is 7

  1. i = 0; Dif = 7-2 = 5 Temp [DIf] = temp[5] = undefined

Temp [arr[I]] = I; Temp [2] = 0 // Hash table stores traversed values and corresponding subscripts

  1. i = 1; dif = 7 – 3 = 4 此时 temp[dif] = temp[4] = undefined

Temp [arr[I]] = I; Temp [3] = 1 // The hash table stores the iterated values and their corresponding subscripts

  1. i = 2; Dif = 7-5 = 2 In this case, temp[DIf] = temp[2] = 0

Temp [dif], temp[dif], temp[0, 2], temp[dif], temp[dif], temp[0, 2], temp[dif], temp[dif], temp[dif], temp[0, 2], temp[dif], temp[dif], temp[dif]

reference

  • The sum of N number
  • The sum of two Numbers

conclusion

  • After the double number to realize the idea: Double traverse | Single-layer traversal (with object storage) | Double pointer