Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

TL:DR

The essence of a pointer is to remember the progress of an array traversal, thereby reducing the scope for invalid traversals.

When traversing an ordered array, larger and smaller values are determined because of the order, so you can use Pointers to remember the progress of traversing the array, thus reducing the scope for invalid traversals

On an array, a single pointer points to the beginning (or end) and then moves. When the pointer moves outside the array, it completes the array.

In an array, if two Pointers appear at both ends, as the two Pointers move, the range of elements in the middle will become smaller until the Pointers are adjacent or coincide. This method is also called colliding Pointers.

When dealing with summation or scaling problems, if the array is unordered, try ordering before using Pointers.

Exercise: Ordered array merge

The first thought I saw was sort:

var merge = function (nums1, m, nums2, n) {
  // Delete the superfluous elements in num1 and insert the elements in num2 into num1nums1.splice(m,n,... nums2.slice(0,n))
  / / sorting
  nums1.sort((a,b) = >a-b)
};
Copy the code

The splice method must be able to delete and add. The first index indicates the position to be operated on (where the elements must be changed), the second index indicates the deletion of the following elements, and the following indexes indicate the inserted elements.

But in fact, now that we have an order, we should take full advantage of this condition to reduce invalid traversal. Upper pointer method!

Num1 = num1 = num1 = num1 = num1 = num1

  • Nums1 and nums2 are ordered by themselves, so the numbers are arranged from smallest to largest, i.e., the largest number is always at the end
  • I’m just going to plug the big numbers in num1
  • A pointer to the last digit of num1. A position pointing to the last digit of num2. There is also a pointer to where to fill in num1
  • As long as the pointer is there, it keeps comparing the first two Pointers, filling in the next one, and moving the pointer
  • If the pointer 1 is less than 0, it means that num1 has been traversed, and num2 is not traversed
  • If 2 is less than 0, it means that num2 is done, so it’s all in num1

var merge = function (nums1, m, nums2, n) {
  // Pointers start at the end
  let pointer1 = m - 1;
  let pointer2 = n - 1;
  let fillPointer = m + n - 1;
  / / has been traversal, until you have an array traversal, traverse through the performance of an array is: pointer1 < 0 | | pointer2 < 0
  while (pointer1 >= 0 && pointer2 >= 0) {
    // if the num1 pointer points to a larger value, it fills that value and moves the pointer to indicate that the value is no longer traversed
    if (nums1[pointer1] >= nums2[pointer2]) {
      nums1[fillPointer] = nums1[pointer1];
      pointer1--;
      fillPointer--;
    } else {
      / / in the same waynums1[fillPointer] = nums2[pointer2]; pointer2--; fillPointer--; }}// When nums1 is traversed first, insert the untraversed values in nums2 into nums1
  if (pointer1 < 0) {
    // pointer2 >=0 is a traversal condition
    while (pointer2 >=0) { nums1[newPointer] = nums2[pointer2]; pointer2--; newPointer--; }}};Copy the code

Obviously space O(1), time O(m+n).

Check out the official video

Exercise: Sum of three numbers

Violence, I’m not going to say, triple traversal, just throw out the right combination, order n^3 time.

Clearly, this is not the desired process.

Sum of two numbers, Map, space for time. But the sum of three numbers, there are two numbers that are not fixed, is not suitable for maps, so arrays and sums, think of Pointers.

The prerequisite for Pointers is an ordered array, so sort first and then use Pointers

  • Array sort first
  • Fix nums[I] and use left and right Pointers to both ends after nums[I]
  • If the sum of the three numbers is greater than 0, the right pointer moves backward; if the sum is less than 0, the left pointer moves forward; if the sum is equal to 0, the index is saved and the left and right Pointers move
  • If nums[I] is greater than 0, it stops traversal, because subsequent values are bound to be greater than 0
  • For duplicate problems: left and right Pointers and I, skip as long as they match the previous values.

var threeSum = function (nums) {
  // nums = Array.from(new Set(nums));
  nums.sort((a, b) = > a - b);
  let res = [];
  let len = nums.length;
  // I is a pointer to the first fixed number
  for (let i = 0; i < len - 2; i++) {
    if (nums[i] > 0) {
      break;
    }
    If (I >0) {// if (I >0) {// if (I >0)
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    // L is the left pointer
    let L = i + 1;
    // R is the right pointer
    let R = len - 1;
    // If L>=R, array traversal is complete
    while (L < R) {
      const sum = nums[L] + nums[R] + nums[i];
      // If the value is greater than 0, the right pointer is backward
      if (sum > 0) {
        // This sentence is to be repeated. If I have the same value, I'm going to skip it, and I'm going to have to add L
        while (L < R && nums[R] === nums[R - 1]) R--;
        R--;
      } else if (sum < 0) {
        while (L < R && nums[L] === nums[L + 1]) L++;
        L++;
      } else {
        res.push([nums[i], nums[L], nums[R]]);
        while (L < R && nums[L] === nums[L + 1]) L++;
        L++;
        while (L < R && nums[R] === nums[R - 1]) R--; R--; }}}return res;
};
Copy the code

Time is reduced to O(n^2).

Check out the official video

reference

  • The front-end algorithm and data structure of xiuyan