LeetCode-双指针

一. 前言

​ LeetCode的题目还是挺多的，但漫无目的地刷题其实意义不大，更多的还是需要在适量的题目之后，进行归纳总结，比如这篇文章就是对“双指针”相关的题目进行归纳总结。

​ 参考：①https://github.com/CyC2018/CS-Notes/tree/master/notes

​ ②https://leetcode-cn.com/circle/article/GMopsy/

二. 什么是双指针？

​ 在Java里并不像C++那样具备完全的“pointer”功能，但实际上把它当作index就差不多了。采用最简单的暴力法，通常都只有一个指针（想想那两层甚至是三层的for循环，实际上就只有一个指针指向一个确切的数据）。有的时候只要多增加一个变量（指针），那么就能很好的优化算法效率。

​ 双指针通常有两种。①左右指针。通常用于数组，字符串的问题，比如二分查找，查找回文串，子序列等等。②快慢指针。通常用于链表的问题，使用快慢指针有时候可以巧妙地解决很多链表问题。

​ 理论应该很好理解，尤其只要在leetcode上刷过一定数量题目的朋友都应该大致了解了。那么现在就拿几道实际的题目进行操作。

三. LeetCode 167. 有序数组的Two Sum

167. Two Sum II - Input array is sorted (Easy)

Leetcode / 力扣

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目描述：在有序数组中找出两个数，使它们的和为 target。

分析: 这里需要注意的是，题目的一个条件是“有序数组”，一般这种有序的数组，都可以采用双指针来进行解决。

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。

数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。

总结：这题没什么难度，即使直接暴力法也能解决，或者使用额外的哈希表作为存储空间都可以，双指针也不难想到。下面是双指针的示意图：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while(true) {
            int tmp = numbers[left] + numbers[right];
            if (tmp == target)
                return new int[] {left + 1, right + 1};
            else if (tmp < target)
                left++;
            else
                right--;
        }
    }
}

四. LeetCode 633. 两数的平方和

633.Sum of Square Numbers (Easy)

Leetcode / 力扣

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

题目描述：判断一个非负整数是否为两个整数的平方和。

分析：可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。

本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。

本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。

因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。

总结：像这种可行解是全体整数的时候（如果严谨一点应该是sqrt(Integer.MAX_VALUE))，暴力法显然会超时，哪怕你提前把上界限定为sqrt(n),可是在暴力法的时间复杂度为O(n^2)的情况下，需要的时间依然很长导致超时（n可能会很大）。这时候第一想法可能会是使用额外的空间，使用数据结构来存储，确实能比暴力法优化很多。如果是使用List，那么就需要用到contains方法，也就是O(n)，所以这时候的效率提升并不明显，仍然会超时。而如果使用Set，Set的contains方法使用的是哈希表，理论上是O(1)，所以时间复杂度为O(sqrt(target)) * O(1)。这时候可以AC，并不会超时，但是随着target比较大的时候，哈希表的时间不能完全忽略，所以效率还是比双指针低。

哈希表方法： 77ms

class Solution {
    public boolean judgeSquareSum(int c) {
        Set<Integer> set = new HashSet<>();
        int temp = (int)Math.floor(Math.sqrt(c));
        for (int i = 0; i <= temp; i++) 
            set.add(i * i);
        Iterator it = set.iterator();
        while (it.hasNext()) {
            if (set.contains(c - (int)it.next()))
                return true;
        }
        return false;
    }
}

双指针方法： 2ms

class Solution {
    public boolean judgeSquareSum(int c) {
        int left = 0, right = (int)Math.sqrt(c);
        while(left <= right) {
            int tmp = left * left + right * right;
            if (tmp == c)
                return true;
            else if (tmp < c)
                left++;
            else
                right--;
        }
        return false;
    }
}

五. LeetCode 345. 反转字符串中的元音字母

345.Reverse Vowels of a String (Easy)

Leetcode / 力扣

Given s = "leetcode", return "leotcede".

题目描述：把字符串里的所有元音字符倒转，即第一个元音字符与最后一个倒转，第二个与倒数第二个倒转。元音字母包括大小写，所以不能只考虑小写。

分析: 使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。

为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。

• 时间复杂度为 O(N)：只需要遍历所有元素一次
• 空间复杂度 O(1)：只需要使用两个额外变量

总结：最直观的方法，应该是直接创建一个List，把所有元音字符的indexs存储起来，然后逐个反转。经过测试，效率跟双指针方法差不多。但是这里要明白，双指针并非只能用于数组链表，对于字符串也是很有效的工具，因为字符串可以很容易地转换成字符数组。而且双指针还有一个优势是，消耗的空间较少。如果要存储indexs，需要一个额外的List，而双指针只需要两个简单的变量。（而这道题的HashSet，任何方法都要用到）

class Solution {
    public String reverseVowels(String s) {
        Set<Character> set = new HashSet<>(
            Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        
        int left = 0, right = s.length() - 1;
        char[] result = new char[s.length()];	// 使用char数组存储临时数据
        while (left <= right) {
            char l = s.charAt(left);
            char r = s.charAt(right);
            if (!set.contains(l))
                result[left++] = l;
            else if (!set.contains(r))
                result[right--] = r;
            else {
                result[left++] = r;
                result[right--] = l;
            }
        }
        return new String(result);
    }
}

六. LeetCode 680. 回文字符串

680.Valid Palindrome II (Easy)

Leetcode / 力扣

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

题目描述：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

分析：所谓的回文字符串，是指具有左右对称特点的字符串，例如 “abcba” 就是一个回文字符串。

使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。

本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。

总结：接着上一题，双指针在字符串题型里很有效，而对于回文这个定义，双指针更是非常适合用于检测回文。因而这道理最应该直接想到的方法便是双指针法。除此之外，这种要考虑不止1种情况的情形（删左/删右），最好就直接新建一个helper方法，直接同时调用，将结果取或即可。如果直接用for循环，那么还得慢慢考虑如果改变left，right指针值的变化。

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            char l = s.charAt(left);
            char r= s.charAt(right);
            if (l != r)
                return helper(s, left + 1, right) || helper(s, left, right - 1);
            left++;
            right--;
        }
        return true;
    }

    public boolean helper(String s, int left, int right) {
        while (left < right) {
            char l = s.charAt(left++);
            char r = s.charAt(right--);
            if (l != r)
                return false;
        }
        return true;
    }
}

七. LeetCode 524. 最长子序列

524.Longest Word in Dictionary through Deleting (Medium)

Leetcode / 力扣

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"

题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。

分析：通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。

总结：除了回文串，字符串子序列的相关问题也很适合使用双指针解决。（不一定要左右指针，这里用的是同向指针，当两个指针指向的字符相同，则同时移动两个指针。如果不相同，则移动指向s的指针，这样可以检测t是否为s的子序列subsequence。时间复杂度为O(n),空间复杂度为O(1)。

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String longestWord = "";
        for (String str: d) {
            int longLength = longestWord.length();
            int currentLength = str.length();
            if (longLength > currentLength || (longLength == currentLength &&
                longestWord.compareTo(str) <= 0))
                continue;	// 不符合题目要找的最长要求，直接pass
            if (isSequence(s, str))
                longestWord = str;
        }
        return longestWord;
    }

    public boolean isSequence(String s, String current) {
        int i = s.length() - 1, j = current.length() - 1;
        while ( i >= 0 && j >= 0) {			// 双指针检测是否为subsequence
            if (s.charAt(i) == current.charAt(j)) 
                j--;			// 二者相同，j指针移动
            i--;				// 不管相同与否，i指针都要向前移动
        }
        return j < 0;		// 如果i，j从0开始，这里的判定就是 j == current.length()
    }
}

八. LeetCode 88. 归并两个有序数组

88.Merge Sorted Array (Easy)

Leetcode / 力扣

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

题目描述：把归并结果存到第一个数组上。

分析：这道题的难点在于，不适用额外的存储空间，直接存储到nums1数组上。虽然可以直接偷懒，偏要用额外空间，那么题目也能很快完成，只是这样失去了很多意义，毕竟如果只为了AC，直接一句System.arraycopy，然后Arrays.sort就可以AC了，但这又何必。这道题的核心思想首先是归并，归并实际上就是对两个数组同时操作，也就是使用双指针操作。同时关键又是有序数组，更没有理由放弃双指针了。值得注意的是，需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。(从m + n - 1开始存放数据，这样刚好可以存放m + n个数据，避免了多余的0影响了结果。虽然LeetCode的所有测试用例都没有考虑0数量大于n的情况，默认等于n，但显然题目并没有这个意思。总而言之，严谨一点~)

总结：归并，有序数组，双指针很合适。

class Solution {
    // 从尾部开始进行遍历即可
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1;
        int index2 = n - 1;
        int current = m + n - 1;
        while (index1 >= 0 || index2 >= 0) 
            if (index1 < 0) 
                nums1[current--] = nums2[index2--];
            else if (index2 < 0) 
                nums1[current--] = nums1[index1--];
            else if (nums1[index1] >= nums2[index2]) 
                nums1[current--] = nums1[index1--];
            else
                nums1[current--] = nums2[index2--];
    }
}

九. LeetCode 141. 判定链表中是否含有环

141.Linked List Cycle (Easy)

Leetcode / 力扣

题目描述：RT

分析：直接循环查看是否到达null，肯定不行，因为会超时。当然，如果你能解决传说中的停机问题，你可以试试。这道题应该是大部分人第一次接触到”双指针“概念的题，快慢指针。使用双指针，一个slow指针每次移动一个节点，一个fast指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。证明应该很直观，如果存在环，两个指针最后一定会在环里同时移动，一个快一个慢，最后一定会在某个时刻二者相遇。如果没有环，slow指针永远不会追上fast指针，并且fast指针会到达end，结束循环。

总结：链表的快慢指针，也是巧妙解决链表问题的好办法。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) { // fast只要不为null, slow一定不为null
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow)
                return true;
        }
        return false;
    }
}

十. LeetCode 142. 判定链表中是否含有环，如果有，返回环的入口

142.Linked List Cycle Ⅱ (Medium)

Leetcode / 力扣

题目描述：RT

分析：这题仍然是用快慢双指针解决。只是当我们判断二者相遇的时候，如何获得环的入口？答案是，把其中一个指针放到head处，然后两个指针以同样的速度（每次行走1个单位）前进。当它们第二次相遇的时候，所在的地方就是环的入口。因为这样并不直观，因此我们可以给出一个证明。

证明：假设链表在进入环之前的长度为a，环的长度为b。（a，b均为未知数）

假设当slow指针 走了s 距离的时候，二者相遇，此时显然可得：

fast指针 走的距离：f = 2s

又易知，fast指针 肯定比slow指针 多走了n圈环 的距离，所以可得： f = s + nb （n 为正整数）

两式结合可得： s = nb

同时由定义可得，当指针处于环入口，那么此时指针一定走了 a + mb 的距离 （m为非负整数），所以现在slow指针 已经走了nb 的距离，只要它再走a 距离，便能到达环入口。但在a是未知数的情况下，如何确定slow 再走a 距离？

答案是：将fast指针重置在head处，因为head距离环入口的距离就是a，此时fast指针跟slow指针距离环入口的距离相同，那么只要二者以相同的速度（1个单位）前进，再次相遇的地方就是环入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                break;
        }
        if (fast == null || fast.next == null)  // 无环
            return null;
        fast = head;            // 将fast重置在head
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;    // fast与slow同等速度前进，再次相遇则为环入口
    }
}

十一. 寻找链表的中点，寻找链表的倒数第k个元素

寻找中点： LeetCode | 力扣

寻找倒数第k个元素： 力扣

题目描述：RT。因为比较简单，就放在一起

分析：寻找中点直接使用快慢指针，显然当fast指针到达结尾，slow指针就是指向中点。如果链表的长度是奇数，那么slow就停在中点位置。如果链表的长度是偶数，slow停在两个中间元素的后者，同样符合中点的含义。

对于寻找链表的倒数第k个元素，同样可以用双指针。先让其中一个指针走k步，然后两个指针同时移动，当第一个指针到达结尾，第二个指针便到达了倒数第k个元素的位置。

寻找中点：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

寻找倒数第k个元素：

class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head == null)
            return 0;
        ListNode fast = head, slow = head;
        for (int i = 0; i < k; i++)
            fast = fast.next;       // 先让fast走k步
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;      // 当fast到达end(此时fast为null), slow到达倒数第k个
    }
}

十二. 滑动窗口Sliding Windows类题目

简述：LeetCode有一类题型叫Sliding Windows，实际上就是用双指针维护一个范围的数据，然后按照需要移动两个指针，就像一个大小变化的窗口。这类题目也是典型的双指针题目。这类题目在LeetCode有一个非常好的讲解，这里就不讲述滑动窗口的具体思路，可以到这个参考链接 阅读。这里直接给出Java代码。

题目①： LeetCode 76. 最小覆盖字串 题目链接

题目描述：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

分析：双指针的典例。值得注意的是，如果使用HashMap，Integer在大于127之后，不能使用 ”==“来判定，简单地说，就是Integer范围只有在[-128, 127]，才从常量池里拿，否则就是一个对象，需要使用equals方法来判定。具体可以参考这篇文章。

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

class Solution {
    public String minWindow(String s, String t) {
        int[] map1 = new int[58];		// 字母包含大小写，中间还有6个特殊符号
        int[] map2 = new int[58];
        boolean flag = false;			// 用于check最后是否整个字符串s都无法覆盖
        String current = s;				// 表示当前的最小覆盖子串，初始化为s
        for (char c: t.toCharArray())
            map2[c - 'A']++;
        int left = 0, right = 0;		// 滑动窗口双指针
        while (right < s.length()) {
            map1[s.charAt(right) - 'A']++;
            right++;					// 先移动right指针
            boolean flag1 = false;		// 用于判断是否到达了内层while，再改变current的值
            while (helper(map1, map2)) {	// 直到满足覆盖，开始移动left指针
                flag = true;
                flag1 = true;
                map1[s.charAt(left++) - 'A']--;
            }
            if (flag1 && current.length() > (right - left + 1))
                current = s.substring(left - 1, right);	// 更小的覆盖字串
        }
        if (!flag)			// 如果flag为false，说明一次也没有进入内层while，无法覆盖
            return "";
        return current;
    }

    public boolean helper(int[] m1, int[] m2) {
        for (int i = 0; i < m1.length; i++)
            if (m1[i] < m2[i])
            return false;
        return true;
    }
}

---

题目②：LeetCode 438. 找到字符串中所有字母异位词 题目链接

题目描述：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

分析： 这题比上一题简单很多，因为它无须“滑动”，窗口的大小是固定的，我们只需要同时移动双指针即可。

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] s1 = new int[26];			// 小写字母，直接数组就可以替代HashMap
        int[] s2 = new int[26];
        int left = 0, right = p.length(), length = s.length();
        if (length < p.length())
            return res;
        for (int i = 0; i < right; i++) {
            s1[s.charAt(i) - 'a']++;	// 初始化，二者都是前right个字符
            s2[p.charAt(i) - 'a']++;
        }
        while (right <= length) {	// 因为循环里的break条件是 right + 1，所以这里有等号
            if (check(s1, s2))
                res.add(left);
            s1[s.charAt(left++) - 'a']--;	// 移动过程，减去第一个字符
            if (right + 1 > length)			// 提前考虑是否有下一个字符
                break;
            s1[s.charAt(right++) - 'a']++;	// 移动过程，加上下一个字符
        }
        return res;
    }

    public boolean check(int[] s1, int[] s2) {
        for (int i = 0; i < 26; i++)
            if (s1[i] != s2[i])
                return false;
        return true;
    }
}

---

题目③：无重复字符的最长子串 题目链接

题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

分析：这题跟第一题很像，也是典型的滑动窗口

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, res = 0;
        Set<Character> set = new HashSet<>();
        while (right < s.length()) {
            char c = s.charAt(right++);			// 移动right指针,直到有重复
            while (set.contains(c)) 
                set.remove(s.charAt(left++));	// 移动left指针,直到无重复
            set.add(c);
            res = res >= (right - left) ? res : right - left;
        }
        return res;
    }
}

十三. 其他

双指针还有一个很重要的应用，就是二分查找。但二分查找也是一个专门的题型，所以决定在二分查找篇章再写。