双指针系列

关于双指针大致可分为四大类型
1. 快慢指针  对应题号 27， 283， 26， 80， 287
2. 左右指针  对应题号 167， 15， 16， 18， 11， 42
3. 后序指针  对应题号  88， 977
4. 其它类型  对应题号 459， 28

此贴会着重介绍快慢指针系列。
快慢指针最直观的一题是关于linked list的题目LeetCode 141 题
顾名思义，就是定义两个指针，一个跑两个单位，一个跑一个单位直到达到目地为止

我们先来看27题 Remove Element
这道题的题意就是，在同一个array中删除指定的val。难点有2。第一是在同一array 操作，不能产生额外的space，第二是删除后，若后面还有element还要把删除空的位置补齐。

思路就是
1.定义一个Slow 指针 K = 0
2. 循环整个array （相当于一个快指针）
3. 如果当前点不等于 指定的 val 则把慢指针 位置 设置为快指针位置的value

来看代码

1. 
   
2. class Solution {
   
3.     public int removeElement(int[] nums, int val) {
   
4.         int k = 0;
   
5.         for(int i = 0; i < nums.length; i++){
   
6.             if(nums[i] != val){
   
7.                 nums[k++] = nums[i];
   
8.             }
   
9.         }
   
10.         return k;
    
11.     }
    
12. }
    

复制代码

那么练习一下 可尝试一下283题
这道题就是把所有的0 放到末尾，有了上面的例子这道题就是很简单。多了一点就是要k跑完之后要一直跑到array末尾把0都续上

1. 
   
2. class Solution {
   
3.     public void moveZeroes(int[] nums) {
   
4.         int k = 0;
   
5.         for(int i = 0; i < nums.length; i++){
   
6.             if(nums[i] != 0){
   
7.                 nums[k++] = nums[i];
   
8.             }
   
9.         }
   
10.         while(k != nums.length) nums[k++] = 0;
    
11.     }
    
12. }
    

复制代码

26 和 80题都是差不多思路 也就不多说上code
Leetcode 26

1. 
   
2. class Solution {
   
3.     public int removeDuplicates(int[] nums) {
   
4.         int k = 1;
   
5.         for(int i = 1; i < nums.length; i++){
   
6.             if(nums[i] != nums[k - 1]){
   
7.                 nums[k ++] = nums[i];
   
8.             }
   
9.         }
   
10.         return k;
    
11.     }
    
12. }
    

复制代码

Leecode 80

1. 
   
2. class Solution {
   
3.     public int removeDuplicates(int[] nums) {
   
4.         int k = 2;
   
5.         for(int i = 2; i < nums.length; i++){
   
6.             if(nums[i] != nums[k - 2]){
   
7.                 nums[k ++] = nums[i];
   
8.             }
   
9.         }
   
10.         return k;
    
11.     }
    
12. }
    

复制代码

这几道题里最难得一题就是287了。这道题的思路和142这道题是一样的。如果有duplicate就说明会有一个环存在。
具体的数学公式请看我上一个帖子
传送门 https://www.1point3acres.com/bbs/thread-816987-1-1.html

1. 
   
2. class Solution {
   
3.     public int findDuplicate(int[] nums) {
   
4.         int slow = nums[0];
   
5.         int fast = nums[nums[0]];
   
6.         //找到 两点相遇点
   
7.         while(slow != fast){
   
8.             slow = nums[slow];
   
9.             fast = nums[nums[fast]];
   
10.         }
    
11.         slow = 0;
    
12.        //慢指针重新出发 当和fast相遇的时候就是结果出现的时候
    
13.         while(slow != fast){
    
14.            slow = nums[slow];
    
15.             fast = nums[fast];
    
16.        }
    
17. 
    
18. 
    
19.         return fast;
    
20.     }
    
21. }
    

复制代码