Front end data structure and algorithm (12): Interesting algorithm-multi-pointer and sliding window

Preface

If you talk about how to use algorithms to solve certain problems efficiently and interestingly, then multi-pointer and sliding algorithms are definitely among the best. This is also the most interesting point when the author first came into contact with the algorithm, because the problem to be solved is familiar, but the formula is completely different. In this chapter, we start from a simple intersection problem and realize step by step that multiple pointers and sliding windows can solve certain problems. Ingenious and efficient in the problem, this chapter mainly uses the solution LeetCodeof the high-frequency problems as a reference~

Multi-pointer

349-The intersection of two arrays↓

Given two arrays, write a function to calculate their intersection.

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Source: LeetCode
Link: https://leetcode-cn.com/problems/intersection-of-two-arrays

Violent solution:

setSimply put the elements common to the two arrays into one array for deduplication, and deduplication needs to be used , then directly save it to the end set. code show as below:

Solution 1:

var intersection = function (nums1, nums2) {
  const set = new Set()
  nums1.forEach(num => {
    if (nums2.includes(num)) {
      set.add(num)
    }
  })
  return [...set]
};

The following simply assumes that the lengths of the two arrays are both n. The solution is a violent solution. It requires a double loop and includesneeds to be searched in the array. Therefore, it is also traversed internally. The final complexity is O(n²), is there a more efficient solution?

Binary search:

Of course, because it is a search problem, we can sort the two arrays separately, and then use the binary search method we learned in the previous chapter to search and replace includes, then the final solution can be optimized to the O(nlogn)level, the code is as follows:

Solution 2:

var intersection = function (nums1, nums2) {
  nums1.sort((a, b) => a-b)
  nums2.sort((a, b) => a-b)
  const set = new Set()
  nums1.forEach(num => {
    if (binarySearch(nums2, num)) {
      set.add(num)
    }
  })
  return [...set]
};

function binarySearch(arr, target) {//binary search
  let l = 0;
  let r = arr.length
  while (r> l) {
    const mid = l + (r-l)/2 | 0
    if (arr[mid] === target) {
      return true
    } else if (arr[mid]> target) {
      r = mid
    } else {
      l = mid + 1
    }
  }
  return false
}

1. data preprocessing, the final lines of code than the method 1a lot more, but the overall complexity is 3more O(nlogn)than O(n²)a lot faster, and more efficient solution it?

Double pointer:

Of course, you can also use a double pointer solution. 1. sort the two arrays, and then use the two pointers to point to the beginning of the two arrays respectively. Whose value is smaller, who slides backwards, encounters the same element. Put setit in until one of the two arrays ends. code show as below:

Solution 3:

var intersection = function (nums1, nums2) {
  nums1.sort((a, b) => a-b)
  nums2.sort((a, b) => a-b)
  let i = 0;
  let j = 0;
  const set = new Set()
  while (i <nums1.length && j <nums2.length) {//There is one to end the loop
    if (nums1[i] === nums2[j]) {//Find the intersection
      set.add(nums1[i])//Put into set
      i++
      j++
    } else if (nums1[i]> nums2[j]) {//Whoever has a smaller value, move with +1
      j++
    } else {
      i++
    }
  }
  return [...set]
};

The overall complexity needs to sort the two arrays quickly, and then the double pointer must complete the two arrays. The final complexity is O(nlogn) + O(nlogn) + 2nthat although the overall complexity is still O(nlogn), the efficiency will be better than binary search.

167-Sum of two numbers II-Input ordered array ↓

Given an ordered array that has been arranged in ascending order, find two numbers so that their sum is equal to the target number.
The function should return these two subscript values ​​index1 and index2, where index1 must be less than index2.

Description:
The returned subscript values ​​(index1 and index2) are not zero-based.
You can assume that each input only corresponds to a unique answer, and you cannot reuse the same elements.

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is equal to the target number 9. Therefore index1 = 1, index2 = 2.

Source: LeetCode
Link: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

It is natural to think of a violent solution, a two-layer loop traversal, and the final complexity is O(n²), but this is not what we thought of.

Obviously, the violent solution does not take advantage of the feature of ascending order in the title description , and the final result needs to be searched, so we can naturally think of using the binary search method. This is indeed a faster way of solving problems, which can reduce the final complexity to a O(nlogn)level, and everyone can try to solve it.

Here is a more clever way of solving problems, colliding pointers . We can set the head and tail pointers and compare their sum with the target each time. If it is larger than the target value, the tail pointer moves to the middle to reduce their added sum; otherwise, if their sum is smaller than the target value, the head Move the pointer to the middle, increasing their sum. Because it is an ordered array, there is no need to worry about missing the target value during the move. code show as below:

var twoSum = function (numbers, target) {
  let l = 0//left pointer
  let r = numbers.length-1//right pointer
  while (r> l) {//Cannot r >= l, because the same value cannot be used twice
    if (numbers[r] + numbers[l] === target) {
      return [l + 1, r + 1]
    } else if (numbers[r] + numbers[l]> target) {
      r--//The right pointer moves to the middle
    } else {
      l++//The left pointer moves to the middle
    }
  }
  return []
};

11-The container with the most water ↓

Give you n non-negative integers a1, a2,..., an, each of which represents a point (i, ai) in the coordinates.
Draw n vertical lines in the coordinates. The two end points of the vertical line i are (i, ai) and (i, 0) respectively.
Find two of the lines so that the container that they form with the x-axis can hold the most water.

Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49 
Explanation: The vertical line in the figure represents the input array [1,8,6,2,5,4,8,3,7].
In this case, the maximum value that the container can hold water (shown as the blue part) is 49.

Source: LeetCode
Link: https://leetcode-cn.com/problems/container-with-most-wate

At first glance, this question may be awkward, or it may be a violent solution using a two-layer loop to find each possibility and find the maximum value in it. The interviewer will definitely not be satisfied with this solution.

And for this classic problem, we can also use the collision pointer solution. 1. set the first and last pointers and approach the middle one by one. But the trouble with this problem lies in the problem of who moves and who doesn't move between the two pointers.

After observation, it is not difficult to find that the value pointed to by the pointer, whose value is small, needs to move. Because if the pointer with the larger value moves to the middle, the pointer with the smaller value will not change, and the distance between them will be shortened, and the product will also become smaller. The battle can be solved in one traversal, and the problem-solving code is as follows:

var maxArea = function (height) {
  let max = 0//Save the maximum value
  let l = 0;
  let r = height.length-1
  while (r> l) {//Cannot meet
    const h = Math.min(height[r], height[l])
    max = Math.max(h * (r-l), max)//The capacity is equal to the distance difference * the shorter axis
    height[r]> height[l]? l++: r--//Move the pointer of the low axis
  }
  return max
};

15-sum of three numbers ↓

Give you an array nums containing n integers, and judge whether there are three elements a, b, c in nums such that a+b+c=0?
Please find all the triples that meet the conditions and are not repeated.
Note: The answer cannot contain repeated triples.

nums = [-1, 0, 1, 2, -1, -4]
The set of triples that meet the requirements are:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Source: LeetCode
Link: https://leetcode-cn.com/problems/3sum

It is easy to think of the brute force solution. Using three-level traversal, the possibility of adding up the three numbers is calculated once and extracting the required combination. The complexity of brute force solution is O(n³). If this problem is to return their corresponding subscripts, there is really no way, but since it is to return combined numbers, then we can use the characteristics of ordered arrays or use colliding pointers to solve this problem more efficiently.

First sort the array, and then set up three pointers i、l、r. Each round of the loop index iis fixed, let the lsum jcollide, and finally move the lsum rpointer according to their added sum . And if exactly equal 0, it is found a combination result; if more than 0, it r--allows rthe pointer moves to the middle; is less than 0, to l++let lthe pointer moves to the middle, the complexity of the solution is O(n²). The problem-solving code is as follows:

var threeSum = function (nums) {
  nums.sort((a, b) => a-b)//sort
  const res = []
  for (let i = 0; i <nums.length; i++) {
    let l = i + 1
    let r = nums.length-1
    if (nums[i]> 0) {//If the first element is greater than 0, there is no need to compare it later
      break;
    }
    if (i> 0 && nums[i] === nums[i-1]) {//Skip the same number
      continue
    }
    while (r> l) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {//Just found
        res.push([nums[i], nums[l], nums[r]])
        while (r> l && nums[l] === nums[l + 1]) {//Skip the same number, use one element only once
          l++
        }
        while (r> l && nums[r] === nums[r-1]) {//Skip the same number, use one element only once
          r--
        }
        r--//Narrow the scope
        l++//Narrow the scope
      } else if (sum> 0) {
        r--//The right pointer moves to reduce the sum of the next calculation
      } else {//sum <0
        l++//Move the left pointer, increase the sum of the next calculation
      }
    }
  }
  return res

};

Sliding window

643-Maximum average of sub-array I ↓

Given n integers, find the continuous sub-array with the largest average and length k, and output the largest average.

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average (12-5-6+50)/4 = 51/4 = 12.75

kThe length of the parameter is a sub-array, so it can be regarded kas a window, sliding on the original array, and finding its average value every time it passes through a sub-array. If you use a brute force solution, there will be a problem of repeated calculations, so every time we slide one step, we only need to add new elements, and then subtract the leftmost element of the window.

The problem-solving code is as follows:

var findMaxAverage = function (nums, k) {
  let max = 0
  let sum = 0
  for (let i = 0; i <k; i++) {
    sum += nums[i]//Find the first window first
  }
  max = sum/k//The average value of the first window
  let j = k
  while (nums.length> j) {
    sum += nums[j]-nums[j-k]//add the new element, subtract the leftmost element
    max = Math.max(sum/k, max)//Compare with the average value of the previous window
    j++//Swipe to the right
  }
  return max//return the average value of the maximum window
};

674-The longest continuous increasing sequence ↓

Given an unsorted array of integers, find the longest and continuously increasing subsequence, and return the length of the sequence.

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing sequence is [1,3,5], and the length is 3.
Although [1,3,5,7] is also an ascending subsequence, it is not continuous because 5 and 7 are separated by 4 in the original array.

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing sequence is [2], and the length is 1.

Source: LeetCode
Link: https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence

This problem is solved using a sliding window, the window is defined as two subscript l、r, since it is increasing, then we will compare two adjacent performed when the elements encountered greater than the right-most window value, the index lshift to r, the judge resumed the statistics length. The icons are as follows:

code show as below:

var findLengthOfLCIS = function (nums) {
  let l = 0;
  let r = 0;
  let max = 0;
  while (nums.length> r) {//As long as the window is still active in the array
    if (r> 0 && nums[r-1] >= nums[r]) {//If the element encountered is greater than the rightmost value of the window
      l = r//re-statistic length
    }
    max = Math.max(max, r-l + 1)//The longest length of statistics
    r++//Swipe to the right
  }
  return max
};

209-The smallest sub-array ↓

Given an array containing n positive integers and a positive integer s, find the continuous sub-array with the smallest length satisfying its sum ≥ s, and return its length.
If there is no sub-array that meets the criteria, 0 is returned.

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The sub-array [4,3] is the sub-array with the smallest length under this condition.

Source: LeetCode
Link: https://leetcode-cn.com/problems/minimum-size-subarray-sum

The requirement of the question is to find a continuous sub-array whose sum is greater than or equal to the incoming yes s, so we can still use a sliding window to count the sum in the window. If it is already greater than or equal sto, then the length of the window is a continuous sub-array at this time length.

When a continuous sub-array is found, let the window on the left slide to the right, subtract the leftmost value, reduce the sum in the window, and slide the window to the right. If another sub-array that meets the conditions is found, compare the length of the previous sub-array and update the size of the minimum window.

A special case is that if the sum of the entire array is smaller than the sum s, then the length of the window cannot be returned, but it is returned directly 0.

code show as below:

var minSubArrayLen = function (s, nums) {
  let l = 0
  let r = 0
  let sum = 0//sum in the window
  let size = nums.length + 1 
//The size of the window, because it is to find the smallest window, so set a window that is +1 more than the largest
//If you can find a sub-array that meets the conditions, the window size will be updated
  while (nums.length> l) {//Let the left boundary be smaller than the entire array, in order to traverse to each element
    if (s> sum) {
      sum += nums[r++]//window sum is less than s, move the right window
    } else {
      sum -= nums[l++]//The window is larger than s, move the left window
    }
    if (sum >= s) {//Find a matching sub-array
      size = Math.min(size, r-l)//Update the value of the minimum window
    }
  }
  return size === nums.length + 1? 0: size
//If the size is equal to the initial value, it means that there is no sub-array that meets the requirements, otherwise it is found
};

3-The longest substring without repeated characters ↓

Given a string, please find out the length of the longest substring that does not contain repeated characters.

Input: "abcabcbb"
Output: 3 
Explanation: Because the longest substring without repeated characters is "abc", its length is 3.

Input: "bbbbb"
Output: 1
Explanation: Because the longest substring without repeated characters is "b", its length is 1.

This question is similar to the previous question. Sliding windows can be used not only on arrays, but also on strings.

The more troublesome part of this question is that you also need to define a setsearch element set. When there is no element in the newly added window , add it and move the window to the right; if there is this element, you need to move the window to setthe position where it appears, that is in setthe left side of the element itself and the window is removed in all, this process is repeated until the window reaches the right end of the string. as the picture shows:

The problem-solving code is as follows:

var lengthOfLongestSubstring = function (s) {
  const set = new Set();
  let l = 0;
  let r = 0;
  let max = 0;
  while (l <s.length && r <s.length) {
    if (!set.has(s[r])) {//If there is no in the lookup table
      set.add(s[r++]);//Add right shift window
    } else {
      set.delete(s[l++]); 
    //Delete from the left until the newly added elements in the lookup table are deleted
    //Then the window will continue to slide right
    }
    max = Math.max(max, r-l);//Update the maximum value
  }
  return max;
};

At last

Many of the above problems also have other solutions or violent solutions. Not only are they limited to multiple pointers and sliding windows that can be solved, but when dealing with difficult problems, there is another way of solving problems for reference, but these two algorithms are capable of processing boundaries. The requirements are quite high. Pay special attention to the meaning of the open/close interval when defining the pointer.

I remembered that the author had to either violently solve the algorithm problem before, or use various traversals to apitinker with it. At that time, I felt that the amount of code was relatively small. However, after a thorough understanding of the algorithm, I realized that less code does not mean high efficiency, and the logical thinking ability to solve problems is the most important.