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