One, foreword

Normally, traversing a array (or string) involves accessing the elements of an array (or string) from front to back with a single pointer. For the following cases, only using a single pointer will increase the time and space complexity:

For example, if two numbers are found so that their sum equals the target number, the single pointer processing requires nested loops, making the time complexity grow to O(n^2);

Another example: flipping an array with a single pointer requires extra memory space, making the space complexity grow to O(n).

The above solution can be optimized using the double pointer technique:

The first example: you can use the array to sort pre-processing, and then create before and after the pointer to the middle traversal, traversal time complexity is O(n), the overall time complexity mainly depends on the sorting algorithm, usually O(nlogn);

In the second example, one pointer is responsible for traversal and the other is responsible for exchanging elements, so that the space complexity is O(1).

There is no complex definition of double pointer, and it mainly deals with two kinds of problems:

Converting nested loops into single loop problems;

The state is recorded by pointer to optimize the space complexity.

The following actual combat analysis will give you a sense of the power of the double pointer.

1. Sum of two numbers II – Enter an ordered array

Given an ordered array arranged in ascending order, find two numbers such that their sum equals the target number. The function should return the two subvalues index1 and index2, where index1 must be less than index2.

The single-pointer approach to this problem can only be solved by nested loops that enumerate the sum of all two numbers at O(n^2).

If the array in question is already an ordered array, create a pointer before and after:

If the number is larger than target, the tail pointer moves forward;

If the sum of the two numbers is less than target, the head pointer moves backward;

The above code successfully reduces the time complexity to O(n) using the double-pointer technique.

const twoSum = (numbers, target) = > {
    const max = numbers.length
    let start = 0
    let end = max -1
    
    while(start< end) {
    const sum = numbers[start] + numbers[end]
    if(sum === target) 
    {
      return [start, end]
    }
    if(sum > target){
      end --
      continue
    }
    if(sum < target) {
      start++
      continue}}}// The sum of the two numbers in this article is an upgrade of the first article
// Time complexity: O (n)
// Space complexity: O (1) is more advanced than map
Copy the code

Remove duplicates from sorted arrays

Given a sorted array, you need to remove repeated elements in place, so that each element appears only once, and return the new length of the removed array.

Instead of using extra array space, you must modify the input array in place and do so using O(1) extra space.

Example 1: Given the array nums = [1,1,2], the function should return the new length 2, and the first two elements of the original array NUMs are changed to 1,2.

You don’t have to worry about elements beyond the new length of the array.

Example 2: Given nums = [0,0,1,1,1,2,2,3,3,4], the function should return the new length 5, and the first five elements of the original array NUMs are modified to 0,1, 2,3, 4.

Description:

Why is the return value an integer, but the output answer an array?

Note that the input array is passed as a “reference,” which means that changes to the input array in the function are visible to the caller.

Use the fast and slow pointer to record the traversal coordinates. Both Pointers start with the first number, and if both Pointers point to the same number, the fast pointer takes a step forward. If not, then both Pointers step forward, and when the fast pointer has traversed the entire array, the current coordinate of the slow pointer is increased by one to give the number of different numbers in the array.

const removeDuplicates = nums= > {
  const max = nums.length
  if (max === 1) {
    return nums
  }
  let slow = 0
  for (let fast = 1; fast < max; fast++) {
    if(nums[fast] ! == nums[slow]) { slow++ nums[slow] = nums[fast] } }return slow + 1;
}
// Time complexity: O (n)
// Space complexity: O (1)
Copy the code

conclusion

The next day, I chose double pointer to learn one of the important means to improve the efficiency of the code: the previous optimized hash map solution adopts the method of space for time. But double pointer can be more optimized, but the premise is that the array must be ordered

❤️ 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 🌹🌹🌹)

Start the LeetCode tour

Reference: Double pointer Technique Easy article