Double pointer

  • Today, we will share a problem solving method in data structure and algorithm — double pointer

26. Remove duplicates from an ordered array

Address: leetcode-cn.com/problems/re…

So for example, that’s kind of what I want to do, and I want to return 4 because I have 4 different numbers

Class Solution {public int Duplicates(int[] nums) {return 0 if(nums.length==0){return 0; Int last = 0; Int fast = 0; // while(fast<nums.length){// If (nums[fast]! = nums[last]){// slow pointer forward by last++; Nums [last] = nums[fast]; } // move the fast pointer forward one bit fast++; } return last+1; }}Copy the code

And the main thing is

// while(fast<nums.length){// If (nums[fast]! = nums[last]){// slow pointer forward by last++; Nums [last] = nums[fast]; } // move the fast pointer forward one bit fast++; }Copy the code
  • Slow and fast Pointers both start from the first element on the left
  • The slow pointer ensures that, from the first element on the left to the element that the full pointer points to, these elements are not repeated

When the fast pointer does not go to the end, the fast pointer goes forward anyway.

  • When the fast pointer points to the same number as the slow pointer points to, it means that the data starts repeating, and the slow pointer ensures that the data does not repeat, so the slow pointer does not move, and the fast pointer continues to move forward
  • When fast numerical and slow pointer to pointer to differ, this means the slow pointer when you need to move forward, pointer forward after a slow, need to slow the pointer to values into a pointer to the fast numerical, because we slow pointer to ensure that begins with the left is not duplicate data

The specific changes are as follows

27. Remove elements

Address: leetcode-cn.com/problems/re…

For example, something like this

class Solution { public int removeElement(int[] nums, int val) { if(nums.length == 0){ return 0; } int slow =0; int fast =0; // while(fast<nums.length){if(nums[fast]! = val){// Set the value to nums[slow] = nums[fast]; // Slow ++; } // fast pointer move fast++; } return slow; }}Copy the code
  • The slow pointer points to numbers that are in the final array after the data to be deleted is deleted
  • When the fast pointer points to the data to be deleted, the slow pointer does not move and the fast pointer moves forward
  • When the fast pointer points to something other than the data to be deleted, we assign the value to the slow pointer, and then move the slow pointer forward one bit, and the fast pointer forward one bit

209. Smallest subarray of length

Address: leetcode-cn.com/problems/mi…

class Solution { public int minSubArrayLen(int target, int[] nums) { if(nums.length == 0){ return 0; } // window left margin int left = 0; Int right = 0; Int sum =0; // Default sliding window length int result = integer.max_value; While (right <nums.length){sum = sum + nums[right]; While (sum >=target){result = math. min(result, right-left +1); Sum = sum-nums [left]; // move the left edge of the sliding window to the right, shrink the sliding window left++; } // slide the right edge of the window right++; } return result == integer.max_value? 0: result; }}Copy the code

The flow is as follows, mainly observe the change of the green sliding window in the figure

487. The maximum number of consecutive 1s II

  • Address: leetcode-cn.com/problems/ma…

class Solution { public int findMaxConsecutiveOnes(int[] nums) { int left = 0; int right = 0; Int zeroCount = 0; int result =0; while(right <nums.length){ if(nums[right] == 0){ zeroCount++; If (nums[left] == 0){zeroCount--; if(nums[left] == 0){zeroCount--; } // move the left pointer left++; } // Update result = math. Max (result, right-left+1); // move the right pointer right++; } return result; }}Copy the code

The flow is as follows, mainly observe the change of the green sliding window in the figure

1004. Maximum number of consecutive 1s III

  • Address: leetcode-cn.com/problems/ma…

The only difference between this problem and the last one is that instead of allowing 1 0 to start with, we have K 0’s

The code doesn’t change much, just from 1 to K. The complete code is as follows

class Solution { public int longestOnes(int[] nums, int k) { int left =0; int right =0; int zeroCount =0; int result =0; while(right<nums.length){ if(nums[right] == 0){ zeroCount++; } while(zeroCount >k){ if(nums[left] ==0){ zeroCount--; } left++; } result = Math.max(result, right - left +1); right++; } return result; }}Copy the code

conclusion

A double pointer is defined as two Pointers to the specified array/list, doing some custom operations.

  • If you want to subdivide, there are three types of double pointer: left and right pointer, fast and slow pointer and sliding window. Generally, the time complexity is O(n) and the space complexity is O(1), which is the subtlety of double pointer
  • Wechat search: Java xiaojie to refueling