双指针：解决数组、链表、字符串力扣7道题解 Java实现

双指针总体上包含两类：快慢指针和左右指针

一、快慢指针（slow & fast）

快慢指针是指两个指针同向而行，一快一慢

例1：力扣第 26 题「删除有序数组中的重复项」https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些。

已经排好序的数组，使用快慢双指针非常方便。

慢指针slow在后，fast在前，fast和slow相等时，fast一直向前走，slow不动；当fast指向的等于数字不等于slow所指，slow++;nums[slow]=nums[fast];(搞不清的时候举个例子，看一下相等和不等时两个指针是怎么变化的)

class Solution {
    public int removeDuplicates(int[] nums) {
        //当数组为空的时候
        if(nums==null){
            return nums.length;
        }
        //数组不为空时
        //见到有序数组就想双指针
        int slow=0;
        int fast=0;
        while(fast<nums.length){
            if(nums[slow]!=nums[fast]){
                slow++;
                nums[slow]=nums[fast];
            }
            fast++;
        }
        //slow是数组下标，需要加一等到有序数组的长度
        return slow+1;

    }
}

例2：力扣第 83 题「删除排序链表中的重复元素」https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

示例1：

示例2：

这道题要注意的时slow指针到最后可能会出现重复的值比如1→2→3→3→null;

所以一定记得每次把slow的next指针置空

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        //当链表为空时、
        if(head==null){
            return head;
        }
        //已排序的链表，双指针，通过改变next指针即可
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null){
            if(fast.val!=slow.val){
                //改变链表的指针
                slow.next=fast;
                //slow++
                slow=slow.next;
            }
            fast=fast.next;
            //[1,1,2,3,3]断开与后边重复元素的连接
            slow.next=null;
        }

        return head;


    }
}

除了上边两道题，对数组链表去重

下边是是数组原地删除

例3：力扣第 27 题「移除元素」https://leetcode-cn.com/problems/remove-element/

如果fast遇到值为val的元素，则直接跳过，否则就赋值给slow指针，并让slow前进一步。

因为第一个值不确定是不是等于val,所以和第一题不同的是slow先赋值，再++；slow因为是后进行++，所以返回的值就是数组的长度。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow=0;
        int fast=0;
        while(fast<nums.length){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;

    }
}

例4：力扣第 283 题 [移动l零] https://leetcode-cn.com/problems/move-zeroes/

跟例3很像，把val的值直接置0

class Solution {
    public void moveZeroes(int[] nums) {
        // 数组为空
        if(nums.length==0){
            return ;
        }
        //数组非空
        int slow=0;
        int fast=0;
        while(fast<nums.length){
            if(nums[fast]!=0){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        for(int i=slow;i<nums.length;i++){
            nums[i]=0;
        }

    }
}

二、左右指针（left & right）

左右指针包含两种，一是指针在两端，相向而行（例5、6）；一是指针在一起，相背而行（例7）；

例5：力扣第 167 题「两数之和 II 输入有序数组」https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

这道还是比较常规的，类似二分法，通过调节left和right就可以调整sum的大小：

class Solution { public int[] twoSum(int[] numbers, int target) { // 法3：双指针，两端两个指针，left+right>target right-1 left+right<target left+1 int left=0; int right=numbers.length-1; while(left<right){ int sum=numbers[left]+numbers[right]; if(sum==target){ //下标从1开始 return new int[]{left+1,right+1}; }else if(sum>=target){ right--; }else{ left++; } } return new int[]{-1,-1}; } }

例6：力扣第 344 题「反转字符串」https://leetcode-cn.com/problems/reverse-string/

class Solution { public void reverseString(char[] s) { //反转字符串，左右指针相向而行 int left=0; int right=s.length-1; while(left<right){ //交换left和right char c=s[left]; s[left]=s[right]; s[right]=c; left++; right--; } }

前变两道题使用的都是相向而行的双指针，下边这道题使用相背而行的双指针
例7：力扣第5题 [ 最长回文字串 ]https://leetcode-cn.com/problems/longest-palindromic-substring/

回文串指的是：正着读和反着读都一样的字符串。比如说字符串aba和abba都是回文串，因为它们对称，反过来还是和本身一样；反之，字符串abac就不是回文串。

这道题的难度在于回文串的长度可能是奇数，也可能是偶数；

利用了从中心向两端扩散的双指针技巧。

这是liweiwei老师的题解，现在根据他的题解三【中心扩散法】进行作答https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

「中心扩散法」的基本思想是：遍历每一个下标，以这个下标为中心，利用「回文串」中心对称的特点，往两边扩散，看最多能扩散多远。

回文串在长度为奇数和偶数的时候，「回文中心」的形态不一样：
【注意】
奇数回文串的「中心」是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
偶数回文串的「中心」是位于中间的两个字符的「空隙」，例如：回文串 "abba" 的中心是两个 "b"，也可以看成两个 "b" 中间的空隙。

class Solution { public String longestPalindrome(String s) { //回文序列指的是正读反读都一样的字符串，比如abba 或者 aba //子串得是连续的 //解题关键在于中心的那个字母，可能是一个也可能是两个 //利用左右指针，从中心向外扩散 String res=""; for(int i=0;i<s.length();i++){ //当回文子序列为奇数时 String s1=centerSpread(s,i,i); //当回文子序列为偶数时 String s2=centerSpread(s,i,i+1); res=res.length() >s1.length() ? res : s1; res=res.length() >s2.length() ? res : s2; } return res; } public String centerSpread(String s,int left,int right){ while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){ left--; right++; } //刚开始的时候 left 和 right 从中间向两侧扩散， //直到 left 和 right 指向的字符不相等的时候停下来。所以「回文」的开始位置是 left + 1（返回数组的第 1 个数），结束位置是 right - 1。 //关于字符串函数substring(start,end) 字符串下标从0开始，包含start,不包含end return s.substring(left+1,right); } }

----------------------------------------------

参考自labuladong老师的https://mp.weixin.qq.com/s/Z-oYzx9O1pjiym6HtKqGIQ

本帖只是一个初学者对于大佬文章的学习笔记，如有错误或者遗漏，感谢指正。

#算法题#