LeetCode 题解记录 - 双指针

发表于 | 分类于 ， | 游览 次

刷题 - 双指针

[TOC]

合并两个有序数组

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

题目描述:

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

解题思路：

跟堆排序中的合并两个有序数组的方法类似。

从尾部进行遍历，比较两个数组的最大值，放入到第一个数组中的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void merge(int[] nums1, int m, int[] nums2, int n) {
    if (nums1 == null || nums2 == null) {
        return;
    }
    int p1 = m - 1;
    int p2 = n - 1;
    while (p1 >= 0 && p2 >= 0) {
        nums1[p1 + p2 + 1] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
    }
    while (p2 >= 0) {
        nums1[p2] = nums2[p2];
        p2--;
    }
}

移除元素

27. 移除元素 简单

题目描述:
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

解题思路:
使用双指针, i 是慢指针, j 是快指针, 原地置换元素, 最后返回新数组的长度.(由于 nums 数组是传参引用, 所以在方法内部修改后, 外部调用时是修改后的数组内容)

1
2
3
4
5
6
7
8
9
public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j ++) {
        if (nums[j] != val) {
            nums[i++] = nums[j];
        }
    }
    return i;
}

无重复字符的最长子串

3. 无重复字符的最长子串 中等

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

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

解答思路：
使用滑动窗口，双指针进行左闭右开[i, j)，每次遍历刷新下标，保证set中不重复，取最长的ans，

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int ans = 0, i = 0, j = 0;
    while (i < n && j < n) {
        if (!set.contains(s.charAt(j))){
            set.add(s.charAt(j++));
            ans = Math.max(ans, j - i);
        }
        else {
            // 有重复的情况下，去掉最左边
            set.remove(s.charAt(i++));
        }
    }
    return ans;
}

进阶版

解答思路：
遇到重复的字符，将滑动窗口的左边直接滑到第一个重复的字符下标。如果 s[j] 在 [i, j) 范围内有与 j’ 相同的字符, 可以直接跳过 [i, j’]范围内的所有元素, 将 i 下标置为 j’ + 1. 使用 HashMap 来存储字符对应的下标.

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int length = s.length(), ans = 0;
    for (int i = 0, j = 0; j < length; j++) {
        char temp = s.charAt(j);
        if (map.containsKey(temp)) {
            i = Math.max(map.get(temp), i);
        }
        ans = Math.max(ans, j - i + 1);
        map.put(temp, j + 1);
    }
    return ans;
}

串联所有单词的子串

30. 串联所有单词的子串 困难

题目描述:
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

1
2
3
4
5
6
7
输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

解题思路:

使用两个 HashMap 保存出现的字符和次数

遍历给定字符(直到总长度 totalLen减去单个待查找字符的长度wordLen), 在内部循环中, 以 wordLen 作为长度切分给定的字符。如果连续子字符中包含查询字符，继续找；如果不包含查询字符，调成内层循环，从下一个字符开始查询。最后内层循环结束后，判断查找次数是否一致，如果是，保存起始下标到结果集中。

代码:

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
28
29
30
31
32
33
34
35
36
37
38
39
public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int wordSize = words.length;
    if (wordSize == 0) {
        return result;
    }
    // words 数组中每个字符的长度都一致, 取第一个
    int wordLength = words[0].length();
    // 字符数组有可能有重复的, 使用 allWordMap 存放每个 word 出现的次数
    HashMap<String, Integer> allWordMap = new HashMap<>();
    for (String word : words) {
        allWordMap.put(word, allWordMap.getOrDefault(word, 0) + 1);
    }
    for (int i = 0; i < s.length() - wordSize * wordLength + 1; i++) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        // 单趟循环中, 成功匹配的次数
        int num = 0;
        while (num < wordSize) {
            // 根据查找字符的长度进行截断
            String word = s.substring(i + num * wordLength, i + (num + 1) * wordLength);
            if (allWordMap.containsKey(word)) {
                hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
                // 还有可能超过 words 中原来的数量
                if (hashMap.get(word) > allWordMap.get(word)) {
                    break;
                }
            } else {
                // 如果没有查询到, 跳过这次循环, 查找下一个字符
                break;
            }
            num++;
        }
        if (num == wordSize) {
            result.add(i);
        }
    }
    return result;
}

旋转链表

61. 旋转链表 中等

题目描述：

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

1
2
3
4
5
输入: 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

解题思路

①：遍历链表，获得链表长度和最后一个节点的地址。

②：计算得到需要移动的次数（k % length）

③：移动，以示例作为例子，k = 2，表示右移两次，可以认为是做了以下三步操作：

  • 末尾节点指向了头部节点：5 -> 1
  • 第三个节点变成了头部节点：head = 3
  • 第二个节点变成了末尾节点：2.next -> null

代码：

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
28
29
30
31
32
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || k == 0) {
        return head;
    }
    int length = 1;
    ListNode tempNode = head;
    ListNode endNode = null;
    while (tempNode.next != null) {
        length++;
        tempNode = tempNode.next;
    }
    endNode = tempNode;
    // 得到需要移动的次数
    int moveNum = k % length;
    if (moveNum == 0) {
        return head;
    }
    // 找到待替换的下标
    int findIndex = 1, index = length - moveNum + 1;
    tempNode = head;
    while (tempNode.next != null) {
        findIndex++;
        if (findIndex == index) {
            endNode.next = head;
            head = tempNode.next;
            tempNode.next = null;
            break;
        }
        tempNode = tempNode.next;
    }
    return head;
}

最小覆盖子串

76. 最小覆盖子串 困难

题目描述：(原题描述不完整，还有很多隐含条件，在评论区找出来的）

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

1
2
3
4
5
6
7
8
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

隐含条件:

1
2
3
4
5
6
7
8
①
输入:
s='a'
t='aa'
输出：
''
②
参数的全集是大写字母和小写字母

解题思路，参考这篇文章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1. 注意到题目的关键："所有字母的最小子串"，也就是说两个串都只能是字母。
2. 于是，可以开辟一个大小为64的数组，来存放数组中字母的频率(Frequency)。准确的说，
   通过字母的ASCII码作为数组的索引，开辟空间的大小为26+6+26=58：26个大写字母，26个小写字母，
   还有中间的6个非字母  A~Z[65~90]  非字母[91~96]  a~z[97~122]
3. 滑动窗口的使用：分三种情况来移动窗口：（这里令当前窗口的左右边界分别为l，r，窗口的大小为winSize=r-l+1）
   1) 当winSize < t.size()  r++;  也就是窗口右边界向右移动
   2) 当winSize == t.size() :
	   2.1) 当窗口中的字符已经符合要求了，直接返回return，已经找到了
	   2.2) 否则r++，窗口右边界向右移动
   3) 当winSize > t.size()
	   2.1) 当窗口中的字符已经符合要求了，l++，窗口左边界向右移动
	   2.2) 否则r++，窗口右边界向右移动
4. 上面是滑动窗口的使用思路，具体实现上有一定的不同，下面是需要考虑到的要点：
   1) 啥叫作窗口中的字符已经符合要求了？
   1) 窗口滑动时的操作是关键
   2) 要考虑到数组越界的问题

代码实现(解答答案中耗时最少的回答）：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public String minWindow(String s, String t) {
    int lenS = s.length(), lenT = t.length();
    if(lenS < lenT){
        return "";
    }
    int[] tCount = new int[256];
    for(int i=0;i<lenT;i++){
        tCount[t.charAt(i)] ++;
    }
    int[] sCount = new int[256];
    int left = 0, right = 0;
    //保存窗口中等于字符串t的字符的数量，当count等于lenT时，说明找到一个子串
    int count = 0;
    int minLen = lenS + 1, start = -1;
    while(left < lenS){
        if(right < lenS && count < lenT){
            //right右滑一格
            char charRight = s.charAt(right);
            sCount[charRight] ++;
            if(sCount[charRight] <= tCount[charRight]){
                count ++;
            }
            right ++;
        }else{
            char charLeft = s.charAt(left);
            //更新最小字串的长度和起始索引
            if(count == lenT && right - left < minLen){
                minLen = right - left;
                start = left;
            }
            //left右滑一格
            sCount[charLeft] --;
            // 这里只会在 sCount 中，被去掉要查询的字符，才会减少窗口中的总数；
            // 如果被去掉是其它无关字符，只需要 left 移动，总量 count 不需要改变
            if(sCount[charLeft] < tCount[charLeft]){
                count --;
            }
            left ++;
        }
    }
    if(start != -1){
        return s.substring(start, start + minLen);
    }
    return "";
}

数组中的 k-diff 数对

532. 数组中的K-diff数对 简单

题目描述：
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

1
2
3
4
5
6
示例 1:
输入: [3, 1, 4, 1, 5], k = 2
输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。

解题思路：

使用 map 保存给定的数组，每个数字出现的次数。根据 k 值判断两个数字间的差值是否符合条件。

代码：

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
28
29
30
public int findPairs(int[] nums, int k) {
    int ans = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    if (k == 0) {
        for (int key : map.keySet()) {
            if (map.get(key) > 1) {
                ans++;
            }
        }
    } else if (k > 0) {
        for (int key : map.keySet()) {
            if (map.containsKey(key + k)) {
                ans++;
            }
        }
    } else {
        for (int key : map.keySet()) {
            if (key >= 0) {
                continue;
            }
            if (map.containsKey(key - k)) {
                ans++;
            }
        }
    }
    return ans;
}

进阶版

将数组排好序之后进行比较：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
public int findPairs(int[] nums, int k) {
    if (k < 0) {
        return 0;
    }
    Arrays.sort(nums);
    int length = nums.length;
    int ans = 0, i = 0, j = 1;
    if (k == 0) {
        while (j < length) {
            if (nums[j] == nums[i]) {
                ans++;
            }
            int a = i++;
            while (nums[i] == nums[a]) {
                i++;
                if (i == length) {
                    return ans;
                }
            }
            j = i + 1;
        }
    } else {
        while (j < length) {
            while (nums[j] - nums[i] < k) {
                j++;
                if (j == length) {
                    return ans;
                }
            }
            if (nums[j] - nums[i] == k) {
                ans++;
            }
            int a = i++;
            while (nums[i] == nums[a]) {
                i++;
            }
        }
    }
    return ans;
}

字符串的排列

567. 字符串的排列 中等

题目描述：

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

1
2
3
4
5
6
7
8
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

解题思路：

由于只包含小写字母，可以使用数组保存待匹配的字符出现的次数。然后通过两个指针的移动，匹配到 s1 长度的 s2 子串。

代码：

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
public boolean checkInclusion(String s1, String s2) {
    int[] count = new int[26];
    char[] pattern = s1.toCharArray();
    char[] str = s2.toCharArray();
    for (int i = 0; i < pattern.length; i++) {
        count[pattern[i] - 'a']++;
    }
    int left = 0, right = 0;
    while (right < str.length){
        if (count[str[right] - 'a'] != 0) {
            count[str[right] - 'a']--;
            right++;
            if (right - left == pattern.length) {
                return true;
            }
        } else if (left == right) {
            left++;
            right++;
        } else {
            count[str[left] - 'a']++;
            left++;
        }
    }
    return false;
}

参考资料：

1、数组—滑动窗口/字母哈希表简单实现 实践leetcode438, leetcode76