2.双指针（二）

https://leetcode-cn.com/tag/two-pointers/

题目汇总

42. 接雨水困难（？？）

61. 旋转链表中等[✔]

75. 颜色分类中等[✔]

76. 最小覆盖子串困难（？？？）

80. 删除排序数组中的重复项 II中等[✔]

86. 分隔链表中等[✔]

88. 合并两个有序数组简单[✔]

125. 验证回文串简单

141. 环形链表简单[✔]

142. 环形链表 II中等

42. 接雨水困难

精选题解的几种解法都超级棒

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]，输出: 6

思路：双指针+动态规划，时间复杂度O(n)

在按列求解的暴力法中，对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度。为了降低时间复杂度，定义两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        for(int i = 1; i < height.length - 1; i++){
            max_left[i] = Math.max(max_left[i-1],height[i-1]);
        }
        for(int  i = height.length - 2; i >= 0; i--){
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);

        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(max_left[i],max_right[i]);
            //只有较小的一列大于当前列的高度才会有水
            if(min>height[i])
                sum += (min - height[i]);
        }
    return sum;
    }
}

61. 旋转链表中等

给定一个链表，旋转链表，将链表每个节点向右移动 k个位置，其中 k是非负数。
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

思路一：官方题解

找到链表的表尾，表尾指向表头，将链表闭合成环，再确定新的链表头和链表尾

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) 
            return null;
        if (head.next == null) 
            return head;
        ListNode cur = head;
        int length = 1;
        while(cur.next!=null){
            length++;
            cur = cur.next;
        }
        cur.next = head;//链表连成环
        for(int i=0;i<length-k%length;i++){
            cur = cur.next;
        }
        ListNode new_head = cur.next;//找到新的链表头
        cur.next = null;//断开
    return new_head;

    }
}

思路二：双指针

先让快指针走 k 个位置，然后两个指针一起走完整个链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了76.85%的用户
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) 
            return null;
        if (head.next == null) 
            return head;
        ListNode cur = head;
        int length = 1;//计算链表总结点数
        while(cur.next != null){
            length++;
            cur = cur.next;
        }
        k %= length;//这步自己没考虑周全，没考虑到k>length的情况
        if(k == 0)
            return head;
        ListNode fast = head;
        ListNode slow = head;
        //快指针先走k步
        while(k>0){
            fast = fast.next;
            k--;
        }
        //两个指针一起移动，当快指针指向尾结点时，慢指针指向新链表头结点的前一个结点
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        //定义一个指针指向新链表的头结点
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
    return newHead;
    }
}

75. 颜色分类中等

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:：不能使用代码库中的排序函数来解决这道题。
输入: [2,0,2,1,1,0]，输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

思路：双指针

初始化0的最右边界：left= 0；初始化2的最左边界：right= n - 1。

class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%
    public void sortColors(int[] nums) {
        if(nums == null || nums.length < 1)
            return;
        int left = 0;
        int right = nums.length - 1;
        int i = 0;
        while(i <= right){
            //nums[i] = 0 时，交换第 i 个 和第 left 个元素，并将 left 指针右移
            if(nums[i] == 0 && i > left){
                int tmp = nums[i];
                nums[i] = nums[left];
                nums[left] = tmp;
                left++;
            }
            //nums[i] = 2 时，交换第 i 个和第 right 个元素，并将 right 指针左移 
            else if(nums[i] == 2 && i < right){
                int tmp = nums[i];
                nums[i] = nums[right];
                nums[right] = tmp;
                right--;
            }else{
                // nums[i] = 1 时，i 指针右移
                i++;
            }
        }
    }
}

76. 最小覆盖子串困难

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路：双指针滑动窗口

大致思路是有的，但是关于滑动窗口的细节问题很难思考全面
代码是评论区BlackLii写的，注释很清楚。

class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了98.99%的用户
    public String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        //维护两个数组，记录已有字符串指定字符的出现次数，和目标字符串指定字符的出现次数
        //ASCII表总长128
        int[] need = new int[128];
        int[] have = new int[128];

        //将目标字符串指定字符的出现次数记录
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }

        //分别为左指针，右指针，最小长度(初始值为一定不可达到的长度)
        //已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的起始位置
        int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0;
        while (right < s.length()) {
            char r = s.charAt(right);
            //说明该字符不被目标字符串需要，此时有两种情况
            // 1.循环刚开始，那么直接移动右指针即可，不需要做多余判断
            // 2.循环已经开始一段时间，此处又有两种情况
            //  2.1 上一次条件不满足，已有字符串指定字符出现次数不满足目标字符串指定字符出现次数，那么此时
            //      如果该字符还不被目标字符串需要，就不需要进行多余判断，右指针移动即可
            //  2.2 左指针已经移动完毕，那么此时就相当于循环刚开始，同理直接移动右指针
            if (need[r] == 0) {
                right++;
                continue;
            }
            //当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时，count才会+1
            //是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符，不需要挨个比对字符出现的次数
            if (have[r] < need[r]) {
                count++;
            }
            //已有字符串中目标字符出现的次数+1
            have[r]++;
            //移动右指针
            right++;
            //当且仅当已有字符串已经包含了所有目标字符串的字符，且出现频次一定大于或等于指定频次
            while (count == t.length()) {
                //挡窗口的长度比已有的最短值小时，更改最小值，并记录起始位置
                if (right - left < min) {
                    min = right - left;
                    start = left;
                }
                char l = s.charAt(left);
                //如果左边即将要去掉的字符不被目标字符串需要，那么不需要多余判断，直接可以移动左指针
                if (need[l] == 0) {
                    left++;
                    continue;
                }
                //如果左边即将要去掉的字符被目标字符串需要，且出现的频次正好等于指定频次，那么如果去掉了这个字符，
                //就不满足覆盖子串的条件，此时要破坏循环条件跳出循环，即控制目标字符串指定字符的出现总频次(count）-1
                if (have[l] == need[l]) {
                    count--;
                }
                //已有字符串中目标字符出现的次数-1
                have[l]--;
                //移动左指针
                left++;
            }
        }
        //如果最小长度还为初始值，说明没有符合条件的子串
        if (min == s.length() + 1) {
            return "";
        }
        //返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串
        return s.substring(start, start + min);
    }
}

80. 删除排序数组中的重复项 II中等

类似题目： 26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3
你不需要考虑数组中超出新长度后面的元素。
与26. 删除排序数组中的重复项类似
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成

思路：双指针

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) 
            return 0;
        if(nums.length < 3)
            return nums.length;
        int j = 1;//慢指针来记录可以覆写数据的位置
        for (int i = 2; i < nums.length; i++)//快指针来遍历整个数组
        {
            if (nums[i] != nums[j-1])
            {
                j++;//慢指针后移一位
                nums[j] = nums[i];//快指针指向的元素覆写入慢指针指向的单元
            }
        }
    return j+1;
    }
}

86. 分隔链表中等

给定一个链表和一个特定值x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路：双指针

用两个指针before 和 after 分别创建两个链表，值小于x的元素在before链表，值大于x的元素在after链表，然后将这两个链表连接即可获得所需的链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public ListNode partition(ListNode head, int x) {
        ListNode beforeHead = new ListNode(0);
        ListNode afterHead = new ListNode(0);//使用哑结点初始化
        ListNode before = beforeHead;
        ListNode after = afterHead;
        while(head != null){
            if(head.val < x){
                before.next = head;
                before = before.next;
            }else{
                after.next = head;
                after = after.next;
            }
            head = head.next;

        }
        after.next = null;
        before.next = afterHead.next;//连接两个链表
    return beforeHead.next;
    }
}

88. 合并两个有序数组简单

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
说明：
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

思路：双指针，时间复杂度 : O(m + n)

从后往前每次比较两个数组的最后一个数，将大的放入末尾指针后再进行比较，假如有nums2有剩余，再放入开头

class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        while(p1 >= 0 && p2 >= 0){
            if(nums1[p1]>nums2[p2]){
                nums1[p] = nums1[p1];
                p1--;
            }else{
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        if(p2 >= 0){
            //表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为p2+1
            //参数src，srcPos，dest，destPos，length: 原数组
            //原数组，从元数据的起始位置开始，目标数组，目标数组的开始起始位置，要copy的数组的长度
            System.arraycopy(nums2, 0, nums1, 0, p2+1);
        }
    }
}

125. 验证回文串简单

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false

思路：双指针

使用两个指针分别指向首尾，如果遇到的字符是数字或字母就进行比较是否相等，如果不是的话就跳过去

class Solution {//执行用时 :5 ms, 在所有 Java 提交中击败了53.91%的用户
    public boolean isPalindrome(String s) {
        if(s.length() == 0)
            return true;
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            if(!isNumOrChar(s.charAt(i))){
                i++;
                continue;//跳过
            }
            if(!isNumOrChar(s.charAt(j))){
                j--;
                continue;
            }
            if(isNumOrChar(s.charAt(i)) && isNumOrChar(s.charAt(j))){
                if(Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))){
                    i++; 
                    j--;
                }
                else{
                    return false;
                }
            }
        }
        return true;

    }
    //判断字符是否为数字或者字母
    public boolean isNumOrChar(char c){
        if(Character.toLowerCase(c) >= 'a' && Character.toLowerCase(c) <= 'z' ||                         Character.toLowerCase(c) >= '0' && Character.toLowerCase(c) <= '9')
            return true;
        return false;
    }
}

141. 环形链表简单

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：双指针

定义两个指针，一快一慢，快指针每次走两步，慢指针每次走一步。如果链表中不存在环，最终快指针将会最先到达尾部，此时返回 false。如果链表中存在环，那么快指针最终一定会追上慢指针。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        } 
        ListNode slow = head;
        ListNode fast = head.next;
       
        while(fast != slow){
            if(fast == null || fast.next == null){
                return false;   
            }
            fast = fast.next.next;
            slow = slow.next;
        } 
    return true;
    }
}

142. 环形链表 II中等

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

思路：双指针

与上一题相比，情况复杂一些
这篇精选解题很好，代码来自这里https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(true){
            if (fast == null || fast.next == null) 
                return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) 
                break;
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

2.双指针（二）

题目汇总

42. 接雨水困难（？？）

61. 旋转链表中等[✔]

75. 颜色分类中等[✔]

76. 最小覆盖子串困难（？？？）

80. 删除排序数组中的重复项 II中等[✔]

86. 分隔链表中等[✔]

88. 合并两个有序数组简单[✔]

125. 验证回文串简单

141. 环形链表简单[✔]

142. 环形链表 II中等

42. 接雨水困难

思路：双指针+动态规划，时间复杂度O(n)

61. 旋转链表中等

思路一：官方题解

思路二：双指针

75. 颜色分类中等

思路：双指针

76. 最小覆盖子串困难

思路：双指针 滑动窗口

80. 删除排序数组中的重复项 II中等

思路：双指针

86. 分隔链表中等

思路：双指针

88. 合并两个有序数组简单

思路：双指针，时间复杂度 : O(m + n)

125. 验证回文串简单

思路：双指针

141. 环形链表简单

思路：双指针

142. 环形链表 II中等

思路：双指针

思路：双指针滑动窗口