【算法】双指针与典型例题

双指针

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算

双指针不一定真的要来个x*搞个指针的，核心还是在于思想

基本概念

对撞指针

在有序数组中，讲指向最左侧的索引定义为left，最右侧的定义为right
然后利用两个指针从两个往中间对数组进行遍历

对有序数组的招数，碰到有序数组可以第一时间想到对撞

与后面那位“快慢指针”相比，它更喜欢解决数组中的问题

//伪代码
function fn (list) {
  var left = 0;
  var right = list.length - 1;

  //遍历数组
  while (left <= right) {
    left++;
    // 一些条件判断 和处理
    ... ...
    right--;
  }
}

快慢指针

但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow）
两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止
如fast每次增长两个，slow每次增长一个。

与前面那位“对撞指针”相比，它更喜欢解决链表问题
以及，它用来寻找一些相等、闭合、“第k个元素”的时候有奇效

它大概可以用在：
判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。
判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了
求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）

题目

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

三数之和题解

先逐步分析一个个问题的解法

1.如何得到符合a + b + c = 0条件的数？
可以转换一下问题：-a = b + c ，我们可以每次都选定一个a，如然后使用双指针去寻找对应的b、c
这样我们就把搜索三个的做法转换为了搜索两个

想要优化查找的进行，显然一个排序过的数组对我们是有利的
而且已排序数组对下一个问题的解决也有利

2.如何让答案“不可以包含重复的三元组”
简单而言就是固定序列
在进行枚举的时候，外面只要保证自己的答案只会搜索到(a,b,c)的排序即可，也就是避免 (b,a,c) (c,a,b) 之类的答案出现

由于我们的数组是已排序数组，所以解决这个问题比想象中简单，我们需要做到两点：
1.检测a,保证每个a只取到过一个数字的值。比如我们在循环中利用i来枚举i，在每次更新后，只要检测i与i-1的关系即可。如果相同就i++去下一位
2.检测b、c,也就是两个双指针也是同理的，更新left/right之后去检测它们和left-1,rgiht+1的关系就好了

如此一来，我们就完成了去重，保证了答案的唯一性

3.其它
基于上面两点，还有其它地方可以优化。
首先是a，如果我们得到的a(假设数组是从小到大排列)是一个大于0的数字，那么我们就可以跳出循环了，毕竟后面的b、c一定不好小于它

在第一重循环就检测a的数值是否重复，以此来节省时间

现在主要的问题已经解决了，接下来按步骤一步步解题就好了

代码如下，注释只简单写了对应的步骤思路

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        //Step1:排序，然后将 a + b + c = 0 转变为-a = b+c 的问题
        Arrays.sort(nums);

        //Step2:大循环,把a从头到尾选择过去(从大到小)
        for(int i = 0 ; i < nums.length -2 ;i++){
            if(nums[i] > 0 )
                break ; //所以数都大于0还找个锤子

            if (i > 0 && nums[i] == nums[i - 1]) 
                continue; //对于相同答案的去重

        //Step3:利用双指针搜 b+c = -a 
                int left = i+1;
                int right = nums.length - 1;
            while(left<right){
                if(nums[left]+nums[right]+nums[i] == 0){
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    //加入答案

                    //更新
                    left++;
                    right--;

                    //在搜索中遇到相同元素的去重
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                }else{
                    //不成立情况下的更新
                    if(nums[left]+nums[right]+nums[i] < 0 )
                        left++ ;

                    if(nums[left]+nums[right]+nums[i] > 0)
                        right--;
                }
            }
        }

        return ans ; 
    }
}

删除重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

删除重复项题解

读题读题，有两个比较重要的地方要注意：
1.nums 已按升序排列
2.不需要考虑数组中超出新长度后面的元素

这意味着：我们只需要按顺序给出有的元素，不必考虑清除后“剩下的地方”的问题
而且这是一个有序数组，我们按顺序检查即可，因此利用快慢指针可以一步到位

解读了题意之后就简单了，我们这么使用指针:
1.slow表示现在标记到的位置，最终slow的下标+1即可得到这个新数组的总长度(因为是下标0开始所以要+1)
2.fast搜索，并发现分界点，到达分界点之后就根据分界点的值更新slow的值与位置。当fast遍历结束，我们的操作结束
3.分界点：nums[fast] != nums[fast-1] ，这说明“nums[fast]”是我们找到的下一个数，更新slow位置并令nums[slow] = nums[fast]

总而言之，意思就是slow来得到目前的数字(因为数组已经排序好了)，而fast在快速搜索，发现前后数字不一的地方(这里就是“重复元素”的分界点)
当我们找到了这个分界点，令slow的位置+1(表更新)，然后用nums[slow] = nums[fast];进行更新
然后无论如何都更新fast即可

完整代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int slow = 0 ;
        int fast = 1 ; 

        if(n == 1 || n == 0)
            return n ;
        
        //利用快慢指针
        while(fast < n){
            if(nums[fast] != nums[fast-1]){
                slow++;
                nums[slow] = nums[fast];
                fast++;
            }else{
                fast++;
            }
        }

        
        return slow+1;
    }
}

两数之和(经典对撞指针)

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

两数之和题解

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length ; 
        int left = 0 ; 
        int right = n - 1 ;
        //对撞撞死
        int sum = 0 ;

        while(left<right){
            sum = numbers[left]+numbers[right] ;

            if(sum == target)
            {
                break ; 
            }else if(sum<target){
                //太小了就移动左边指针扩大
                left++;
            }else{
                right--;
            }
        }
        int [] ans = {left+1,right+1};
        return ans;
    }
}

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

移动零题解

因为想用双指针所以用了双指针，但是个人感觉对双指针的理解还是比较有利的  
主要是利用两个指针checker和book，前者用来遍历，后者用来处理 
核心在于：当checker检测到0的时候，book不会行动
         而当其检测到非零数的时候,book会更新且移动  

当checker移动到终点时，所有应该加入的非零数已经被添加了，那么剩下的就都是0了    
于是，只要把此时book后面的数全部填充为0即可

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length ;
        int checker = 0 ; //查找用
        int book = 0;       //转换用

        while(checker<n){
            if(nums[checker]!= 0){
                nums[book] = nums[checker];
                book++;
            }

            checker++;
        }

        for(int i = book ; i<n ; i++){
            nums[i] = 0 ;
        }
    }
}

其中一个核心理解是：把book独立于checker存在，因为在每次checker检测的时候，book已经跟进更新数据了
而当checker检测到0的时候，book是不会移动的，在检测到0的时刻，checker和book处于同一个下标，
而下一时刻checker++ 而 book不变，这样book就被停留在了一个是0的下标处
而当下一次checker检测到非0数的时候，book执行nums[book] = nums[checker]; 从而抹去了这个零
因为前面的数都排好了，这次也更新了，于是book前进一个下标
如果checker连续检测到了0，那么book就会一直停留，直到checker检测到非0数而更新

反转字符串(经典)

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

反转字符串题解

class Solution {
    public void reverseString(char[] s) {
        int left = 0 ; //左侧指针
        int right = s.length -1 ; //右侧指针
        char temp = 'a' ;
        while(left<right){
            temp = s[left];
            s[left] = s[right] ;
            s[right] = temp ; 
            left++;
            right--;
        }
    }
}

直接极简主义也行，反正一样的，比的又不是代码长度

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}

链表中间节点(经典快慢)

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

链表中间节点题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode sin = head ;
        ListNode dou = head ; 
        ListNode ans ;

        while(dou!=null && dou.next !=null){
            sin = sin.next ; 
            dou = dou.next.next; 
        }

        ans = sin;


        return ans ;  
    }
}

使用两个快慢指针，一个走一步一个走两步。走的快的走到头了就是找到了