LeetCode题解笔记：双指针 - Sanarous的博客

LeetCode题解笔记：双指针

| | ℃
| 2.7k


双指针一般是针对于数组相关的题目的一种解法，主要是解决多重循环遍历数组带来的时间开销，通过两个指针指向不同的元素，运用一些技巧使用双指针协同完成任务可以极大的降低时间复杂度。

有序数组的TwoSum

题目描述

LeetCode第167题

在有序数组中找出两个数，使它们的和为 target。

例如：

1
2
3
Input: numbers={2, 7, 11, 15}, target=9
Output:[1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

解题思路及代码实现

大多数人第一个想法就是直接暴力破解，双重循环轻松搞定，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] twoSum(int[] numbers, int target) {
    if (numbers == null || numbers.length == 0) return null;

    int[] res = new int[2];
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i; j < numbers.length - 1; j++) {
            int temp = numbers[i] + numbers[j+1];
            if (temp == target) {
                res[0] = i + 1;
                res[1] = j + 2;
                return res;
            }
        }
    }
    return null;
}

这种暴力解法的运行时间为101ms，超过5.08%的人的解法，空间复杂度超过63.86%的人。所以显然这种解法效率太低下了。

所以双指针就是为了解决这种时间复杂度太低的问题，由于这是一个排序数组，如果我们使用双指针指向数组的起始位置和终点位置，那么如果二者相加为target，就可以直接返回，否则如果大于target，那么肯定是终点位置的值太大了，那么就让终点位置的指针前移，否则如果二者相加的值小于target，那么肯定是起始位置的值太小了，那么我们需要让起始位置的指针后移，这样时间复杂度可以大大降低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] twoSum(int[] numbers, int target) {
    if(numbers == null || numbers.length == 0) return null;

    int[] res = new int[2];
    int low = 0, high = numbers.length-1;
    while(low < high){
        if(numbers[low] + numbers[high] == target){
            res[0] = low+1;
            res[1] = high+1;
            return res;
        }else if(numbers[low] + numbers[high] > target){
            high--;
        }else{
            low++;
        }
    }
    return null;
}

这种解法瞬间将运行时间降低到1ms，但是这时候还是发现运行时间才超过了56.29%的人，不妨再小小的修改一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] twoSum(int[] numbers, int target) {
    if(numbers == null || numbers.length == 0) return null;

    int[] res = new int[2];
    int low = 0, high = numbers.length-1;
    while(low < high){
+       int temp = numbers[low] + numbers[high];
-       if(temp == target){
            res[0] = low+1;
            res[1] = high+1;
            return res;
        }else if(temp > target){
            high--;
        }else{
            low++;
        }
    }
    return null;
}

这时候就发现运行时间已经到0ms了，并且已经超过了100%的人！那么这就是相对的最优解法。

两数平方和

题目描述

LeetCode第633题

判断一个数是否为两个数的平方和。

例如：

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

解题思路及代码实现

这个题的初始思路应该容易想到，首先给定一个非负整数num时，如果能构成两数平方和等于num，那么这两个数中任意一个数的平方肯定都小于num，反过来就是这两个数中任意一个数都小于num开根号。这种限制数字范围就可以大大降低需要查找的时间复杂度。于是我们还是可以使用双指针思路写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean judgeSquareSum(int c) {
    if(c < 0) return false;

    int low = 0, high = (int)Math.sqrt(c);

    while(low <= high){
        int i1 = (int)Math.pow(low,2);
        int i2 = (int)Math.pow(high,2);
        if(i1 + i2 == c){
            return true;
        }else if(i1 + i2 > c){
            high--;
        }else{
            low++;
        }
    }
    return false;
}

上述代码运行时间4ms，超过68.31%的解法，这是上述使用了Java中的函数Math.pow()，这个函数内部使用了移位算法，虽然会占用一点时间和空间，但是在面对大数据或者高阶次数时会比较高效，但是由于这个题本身只是采用平方，所以我们可以完全可以修改一下代码降低复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean judgeSquareSum(int c) {
    if(c < 0) return false;

    int low = 0, high = (int)Math.sqrt(c);

    while(low <= high){
        int res = low * low + high * high;
        if(res == c){
            return true;
        }else if(res> c){
            high--;
        }else{
            low++;
        }
    }
    return false;
}

修改后代码的运行时间为2ms，超过97.9%的解法，那么这种解法显然达到了最终目的。

反转字符串中的元音字符

题目描述

LeetCode第345题

反转一个字符串中的元音字符

例如：

1
2
Input: "hello"
Output: "holle"
1
2
Input: "leetcode"
Output: "leotcede"

解题思路及代码实现

使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public String reverseVowels(String s) {
    if (s == null || s.trim().equals("")) return s;
    char[] cs = s.toCharArray();
    int low = 0,high = cs.length-1;
    while (low < high) {
        if (isVowelChar(cs[low])) {
            if (isVowelChar(cs[high])) {
                char temp = cs[low];
                cs[low] = cs[high];
                cs[high] = temp;
                low++;
                high--;
            } else {
                high--;
            }
        } else {
            low++;
        }
    }
    return String.valueOf(cs);
}

private boolean isVowelChar(char ch){
    return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
        ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
}

上述代码运行时间2ms，超过98.7%的解法，空间上超过85.55%的解法，已经是很优秀的解法了。

回文字符串

题目描述

LeetCode第680题

可以删除一个字符，判断是否能构成回文字符串。

例如：

1
2
Input: "aba"
Output: True
1
2
3
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

解题思路及代码实现

这个是在回文数的基础上变化的一道题，由于最多只能删除一个字符，所以如果在使用双指针碰到前后字母不一样时，可以多加一道判断即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean validPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
        }
    }
    return true;
}

private boolean isPalindrome(String s, int i, int j) {
    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) {
            return false;
        }
    }
    return true;
}

上述代码运行时间7ms，超过77.74%的解法，但是写法上比较简洁。

判断链表是否有环

题目描述

LeetCode第141题

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

例如：

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

解题思路

这个题与剑指offer上找链表环的起点是一模一样的，都可以使用双指针来找，即假设有两个指针，一个指针一次走一步，一个指针一次走两步，如果两个指针能够相遇，那么说明链表有环，并且可以找到环的起点，如果不能相遇，那么说明链表没有环。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean hasCycle(ListNode head) {
    if(head == null) return false;
    ListNode slow = head;
    ListNode fast = head;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

上述代码运行时间0ms，超过100%的解法，空间占用超过87.71%的解法。

如果要与剑指offer一致，不仅要判断有环，还需要判断环的起始位置，那么思路应该如下：

  1. 首先需要确定有环？这个思路上面已经说过，并且可以通过数学来证明。
  2. 然后如何确定环的节点个数？这个问题也可以用数学证明，若慢指针记作slow，快指针记作fast，那么如果当两个指针相遇时，快指针比慢指针多走了n步，即此时slow = x，fast = 2x，那么2x = x + n，即x = n，那么说明这时候走的步数就是环节点的个数（数学上可证明）。
  3. 最后就是需要确定环的节点个数了。当两个指针相遇时，我们让慢指针位置不动，重置快指针位置到链表起始位置，然后让两个指针以相同的速度前进，当这两个指针相遇时，相遇的节点就是环的起始节点。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode EntryNodeOfLoop(ListNode pHead) {
    if(pHead == null || pHead.next == null){
        return null;
    }
    ListNode slow = pHead;
    ListNode fast = pHead;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            fast = pHead;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            if(slow == fast){
                return slow;
            }
        }
    }
    return null;
}

跟上面思路如出一辙。

最长子序列

题目描述

LeetCode第524题

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

例如：

1
2
3
4
5
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"
1
2
3
4
5
Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

说明:

  1. 所有输入的字符串只包含小写字母。
  2. 字典的大小不会超过 1000。
  3. 所有输入的字符串长度不会超过 1000。

解题思路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public String findLongestWord(String s, List<String> d) {
    if(s == null || d.size() == 0) return null;
    String result = "";
    for(String str : d){
        int i1 = result.length();
        int i2 = str.length();
        if(i1 > i2 || (i1 == i2 && result.compareTo(str) < 0)){
            continue;
        }
        if(isSubStr(str,s)){
            result = str;
        }
    }
    return result;
}

//判断s是否是target的子串
private boolean isSubStr(String str,String target){
    int i = 0, j = 0;
    while(i < str.length() && j < target.length()){
        if(str.charAt(i) == target.charAt(j)){
            i++;
        }
        j++;
    }
    return i == str.length();
}

但是上述运行时间较长，为39ms，仅超过37.26%的解法，说明优化空间还很大。

然后在讨论区看到一个非常简约的解法，不得不感叹算法之路没有终点啊。。

1
2
3
4
5
6
7
8
9
10
11
12
13
public String findLongestWord2(String s, List<String> d) {
    String res = "";
    for (String c : d)
        if ((c.length() > res.length() || c.length() == res.length() && c.compareTo(res) < 0) && isSubseq(c, s))
            res = c;
    return res;
}

private boolean isSubseq(String a, String b) {
    int i = -1, j = -1;
    while (++i < a.length()) if ((j = b.indexOf(a.charAt(i), j + 1)) == -1) return false;
    return true;
}

上述解法运行时间3ms，超过100%的解法，并且空间占用超过了93.35%的解法。

📚  相关文章
如果这篇文章对您很有帮助，不妨
-------------　　　　本文结束　　感谢您的阅读　　　　-------------
0%