Leetcode | 双指针II 88/141/524 | 内含双指针问题的总结 | java实现

本文结尾有关于双指针问题的总结，如有更好的归纳方法，欢迎补充！

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]

参考代码【较为直观的方法】

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
    	//当nums2为空时，直接返回；
    	//这里不用考虑nums1为空，由题不存在这样的情况
        if(n==0){
            return;
        }
        else{
            int[] temp = new int[m+n]; //创建一个临时数组
            int p = 0; //临时数组的下标
            int i = 0; //nums1的指针下标
            int j = 0; //nums2的指针下标
            while(p<m+n){
            	//下面有说明
                if(j==n || nums1[i] < nums2[j] && i!=m) temp[p++] = nums1[i++];
                else if(i==m || nums2[j] <= nums1[i]) temp[p++] = nums2[j++];
            }
            for(int q = 0; q<m+n; q++) nums1[q] = temp[q];
        }

    }
}

NOTES

• 时间复杂度O(2*(m+n))==O(m+n)，空间复杂度O(m+n)

• 这个方法时最直观的，算法是nums1的开头放一个指针，nums2的开头放一个指针，二者比较，将指针所指的较小的数放进临时数组，然后该指针向后移动，直到指针下标等于m或n。
  
  我在这里分了两种情况：

  • 将nums1中的数放入临时数组 的条件
  1. nums1的指针所指的数更小
  2. 并且 nums1的指针的下标不等于m
     说明：如下图所示，此时nums1的指针下标为m，它指向的值将永远小于等于nums2中的数，因此，若不排除这种情况，将导致临时数组被一直填入0
     
  3. 或者 nums2的指针的下标已经等于n（即nums2中的数已经都放进了临时数组，指针超出了数组边界）
  • 将nums2中的数放入临时数组
  1. nums2的指针所指的数更小
  2. 或者 nums的指针的下标已经等于n（即nums2中的数已经都放进了临时数组，指针超出了数组边界）

  ==注意== 标有“或者”的条件需要，放在其他条件之前，这是因为，若不这样将对两个数组进行越界访问，所以如果先判断了满足该条件，就不会在对数组进行访问。
  
  因此，代码如下：

  if(j==n || nums1[i] < nums2[j] && i!=m) temp[p++] = nums1[i++];
  else if(i==m || nums2[j] <= nums1[i]) temp[p++] = nums2[j++];
  

但是这种方法有一定的缺陷，即创建了一个临时数组，提高了空间复杂度。那么有没有可能不创建数组，而是直接边排序边覆盖nums1呢？CyC2018为我们提供了这种算法！

参考代码【更高效的方法】

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1; //nums1指针的下标
        int j = n-1; //nums2指针的下标
        int mergeIndex = m+n-1; //归并后nums1的下标
        while(i>=0 || j>=0){
            if(i<0) nums1[mergeIndex--] = nums2[j--];
            else if(j<0) nums1[mergeIndex--] = nums1[i--];
            else if(nums1[i] >= nums2[j]) nums1[mergeIndex--] = nums1[i--];
            else nums1[mergeIndex--] = nums2[j--];
        }
    }
}

NOTES

• 时间复杂度O(m+n)，空间复杂度O(1)
• 为了避免还没有排序的nums1中的数字被覆盖，所以我被迫想出了第一种方法，我怎么也想不到，指针可以从后往前遍历，是我输了！ 两个指针从后往前遍历数组，代码不难理解
• 值得注意的是，if 语句的条件的顺序，之所以将 i<0 和 j<0 放在最前面，也是为了避免数组被越界访问。同样，判断过了两个指针已经到了数组外面，就不会再访问数组了

141. 环形链表

问题描述

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

示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

参考代码【最基础的做法（没用双指针）】

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> nodesHash = new HashSet<ListNode>();
        while(head != null){
            if(!nodesHash.contains(head)) nodesHash.add(head);
            else return true;
            head = head.next;
        }
        return false;
    }
}

NOTES

• 时间复杂度O(n)，空间复杂度O(n)

• 这个方法主要是使用了哈希表，下面引用官方题解：

  思路：我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。

  算法：从头遍历链表，将结点一个个不重复的放入哈希表。我们通过HashSet类中的contains()方法来逐个判断该结点是不是在哈希表中已经存在，如果不存在就把它放进去；如果存在说明链表中存在一个环。
  
  是不是超级简单！至于为什么使用哈希表，恐怕是contains()这个方法比较方便吧？（如果另有原因，请务必赐教！）

但是这个方法并不能实现空间复杂度为O(1)的进阶问题，我们还需要另辟蹊径！官方题解同样给了我一个新的思路。

参考代码【实现进阶问题的方法（利用双指针】

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        else{
            ListNode l1 = head; //速度较慢的指针
            ListNode l2 = head.next; //速度较快的指针
            while(l2 != null && l1!=null && l2.next!=null){
                if(l1 == l2) return true; //两指针相遇，说明链表带环
                l2 = l2.next.next; //一次走两“格”
                l1 = l1.next; //一次走一“格”
            }
            return false;
        }   
    }
}

NOTES

• 时间复杂度O(n)，空间复杂度O(1)

• 思路：想象一下！龟兔赛跑，如果是环形跑道，速度更快的兔子势必会和乌龟相遇。

• 算法：设置一快（兔子）一慢（龟）的两个指针。快指针通过每次走两“格”实现，慢指针一次走一“格”，如此循环下去。若两指针相等（龟兔相遇），说明链表带环。且当其中一个指针为null（不止如此，下面有说明），即指针指到了链表结尾时，退出循环，同时也说明链表不带环。如下代码：

  ListNode l1 = head; //速度较慢的指针
  ListNode l2 = head.next; //速度较快的指针
  while(l2 != null && l1!=null && l2.next!=null){
      if(l1 == l2) return true; //两指针相遇，说明链表带环
      // l2 = l2.next; //第一次我写成了这样，
                        //显然我没有理解快指针是什么意思
                        //我以为在前面的指针就是快的
      l2 = l2.next.next; //快指针，一次走两“格”
      l1 = l1.next; //慢指针，一次走一“格”
      }
  return false;
  

• 注意！ while的循环条件：不光要两个指针不等于null，还要考虑到链表中只有两个结点的情况，所以要加上快结点的下一个结点也不等于null（l2.next != null）。没有该条件的后果如下：
  

• 也别忘了链表为空的情况嗷

524. 通过删除字母匹配到字典里最长单词

问题描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
输入:
s = “abpcplea”, d = [“ale”,“apple”,“monkey”,“plea”]
输出:
“apple”
示例 2:
输入:
s = “abpcplea”, d = [“a”,“b”,“c”]
输出:
“a”
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

参考代码

public boolean isSubstr(String str, String substr){
    int i = 0;
    int j = 0;
    while(i < str.length() && j < substr.length()){
        if(str.charAt(i) == substr.charAt(j)){
            i++;
            j++;
        }
        else i++;
    }
    if(j == substr.length()) return true;
    else return false;
}
public String findLongestWord(String s, List<String> d) {
    String longestStr = "";
    for(String strInDic : d){
        int longestLen = longestStr.length();
        int strInDicLen = strInDic.length();
        if((longestLen < strInDicLen) || 
            (longestLen == strInDicLen && longestStr.compareTo(strInDic)>0)){
            if(isSubstr(s, strInDic)) longestStr = strInDic;
        }
    }
    return longestStr;
}

NOTES

• 时间复杂度O(n²)，空间复杂度O(n)
• 千万不要被这道题是中等难度而被吓倒了，理清思路后可以发现并不复杂。
  
  思路：解决此题可以分为两个步骤：
  1. 找到“最长”（如果在字典里还有跟它一样长的，就选择字典顺序最小的）的字符串，这个字符串不光要最长，还要具备下面的条件
  2. 是s字符串的子字符串substr，即删除s字符串中的几个字符就能得到substr。这里要用到双指针！
     综上，只有一个字符串先后满足第二个和第一个条件，这才是我们的所求。
     
     明白了解题思路，相信代码也就不难看懂了。看懂容易，我还是建议自己写一遍。这样你才会明白为什么longestStr的初始值为什么是""，而不是d.get(0)；你才会明白为什么在isSubStr()方法中，为什么当 j 等于substr.length()时，才说明 “it is substr” ······

Summary

终于刷完了关于双指针的基本问题，那么今后当我们碰到什么样类型的题时应该想起来使用双指针呢？

• 在一个数组/字符串中，需要两个变量进行某种操作【一个数组/字符串放两个指针】
  • 求和 - 167. 两数之和 II - 输入有序数组 / 633. 平方数之和（平方求和）
  • 调换位置 - 345. 反转字符串中的元音字母（调换元音字母的位置）
  • 比较 - 快速排序算法（比较大小 / 相当于小的数和大的数调换位置）
  • 巧妙的操作 - 141. 环形链表（让一个指针追赶另一个指针，还记得龟兔赛跑嘛）
• 对两个数组/字符串相互进行某种操作【两个数组/字符串各放一个指针】
  • 比较 - 524. 通过删除字母匹配到字典里最长单词（判断一个字符串是不是另一个字符串的子字符串）/ 88. 合并两个有序数组（比较指针所指的数的大小）

总而言之，以我为数不多的做题经验，或许碰到 有序数组 / 调换子母或数字的位置 这样的问题，我们应该想到双指针法。

说明

语言：Java

如有错误，还望指正

参考资料

• CyC2018/CS-Notes/Leetcode题解-双指针
• 141题-力扣官方题解