本文解决的问题: 按主题归纳 双指针、滑动窗口 相关高频题型与通用解法。

适用范围: LeetCode 中文站题目,示例主要使用 Java。

阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。

双指针

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序(原数组的顺序)。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

**进阶:**你能尽量减少完成的操作次数吗?

提示:
1 <= nums.length <= 104

231 <= nums[i] <= 231 - 1

示例:

1
2
3
4
5
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

输入: nums = [0]
输出: [0]

代码:

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
46
47
48
49
50
/**
* 我们创建两个指针i和j,第一次遍历的时候指针j用来记录当前有多少非0元素。
* 即遍历的时候每遇到一个非0元素就将其往数组左边挪,第一次遍历完后,j指针的下标就指向了最后一个非0元素下标。
* 第二次遍历的时候,起始位置就从j开始到结束,将剩下的这段区域内的元素全部置为
*
* @param nums x
*/
public void moveZeroes(int[] nums) {
if (nums == null) {
return;
}
//第一次遍历的时候,j指针记录非0的个数,只要是非0的统统都赋给nums[j]
int j = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}
//非0元素统计完了,剩下的都是0了
//所以第二次遍历把末尾的元素都赋为0即可
for (int i = j; i < nums.length; ++i) {
nums[i] = 0;
}
}


/**
* 这里参考了快速排序的思想,快速排序首先要确定一个待分割的元素做中间点x,然后把所有小于等于x的元素放到x的左边,大于x的元素放到其右边。
* 这里我们可以用0当做这个中间点,把不等于0(注意题目没说不能有负数)的放到中间点的左边,等于0的放到其右边。
* 这的中间点就是0本身,所以实现起来比快速排序简单很多,我们使用两个指针i和j,只要nums[i]!=0,我们就交换nums[i]和nums[j]
* 请对照动态图来理解
*
* @param nums x
*/
public void moveZeroes(int[] nums) {
int l, r = 0;
for (l = 0; l < nums.length; l++) {
if (nums[l] != 0) {
swap(nums, l, r);
r++;
}
}
}


public void swap(int[] nums, int l, int r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明:**你不能倾斜容器。

提示:
n == height.length

2 <= n <= 105

0 <= height[i] <= 104

示例:
2. 盛最多水的容器示例

1
2
3
4
5
6
7
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,
容器能够容纳水(表示为蓝色部分)的最大值为 49。

输入:height = [1,1]
输出:1

代码:

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
/**
* @param height 高度
* @return 面积
* <p>
* 暴力法:
* 遍历数组,计算每个位置的左右指针之间的面积,并更新最大面积。
* <p>
* 优化:
* 双指针法:
* 初始化左右指针,计算初始面积。
* 移动指针:
* 如果左指针的高度小于右指针的高度,则将左指针向右移动,并更新面积。
* 如果左指针的高度大于右指针的高度,则将右指针向左移动,并更新面积。
*循环直到左指针大于右指针。
*/
public int maxArea(int[] height) {
int max = 0, l = 0, r = height.length - 1;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
max = Math.max(max, area);
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return max;
}

三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意:**答案中不可以包含重复的三元组。

提示:
3 <= nums.length <= 3000

105 <= nums[i] <= 105

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
* <p>三数之和</p>
* 排序处理 + 双指针
*
* @param nums 数组
* @return 三元组
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
Map<String, List<Integer>> map = new HashMap<>();
int l, r, k = nums.length - 1;
while (k > 1) {
r = k - 1;
l = 0;
while (l < r) {
int i = nums[l] + nums[r] + nums[k];
if (i == 0) {
String key = String.valueOf(nums[l]) + nums[r] + nums[k];
if (!map.containsKey(key)) {
map.put(key, Arrays.asList(nums[l], nums[r], nums[k]));
}
r--;
l++;
} else if (i > 0) {
r--;
} else {
l++;
}
}
k--;
}
return new ArrayList<>(map.values());
}

/**
* 优化 去除重复元素
* 寻找数组中所有不重复的三元组,这些三元组的和为零
*
* @param nums 输入的整数数组
* @return 返回一个列表,包含所有和为零的不重复三元组
*/
public List<List<Integer>> threeSum(int[] nums) {
// 先排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();

for (int i = 0; i < nums.length; i++) {
// 跳过重复元素
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}

// 双指针,目标是找到 nums[l] + nums[r] = -nums[i]
int l = i + 1, r = nums.length - 1;
int target = -nums[i];

while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
l++;
r--;
// 跳过重复元素
while (l < r && nums[l] == nums[l - 1]) {
l++;
}
while (l < r && nums[r] == nums[r + 1]) {
r--;
}
} else if (sum < target) {
l++;
} else {
r--;
}
}
}

return res;
}

接雨水

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

1 <= n <= 2 * 104

0 <= height[i] <= 105

示例:
4. 接雨水示例

1
2
3
4
5
6
输入:height = [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 个单位的雨水(蓝色部分表示雨水)。

输入:height = [4,2,0,3,2,5]
输出:9

代码:解法

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
public int trap(int[] height) {
int n = height.length;
int res = 0;
// 左右指针:分别指向左右两边界的列
int left = 0, right = n - 1;
// 左指针的左边最大高度、右指针的右边最大高度
int leftMax = height[left], rightMax = height[right];
// 最两边的列存不了水
left++;
right--;
// 向中间靠拢
while(left <= right){
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if(leftMax < rightMax){
// 左指针的leftMax比右指针的rightMax矮
// 说明:左指针的右边至少有一个板子 > 左指针左边所有板子
// 根据水桶效应,保证了左指针当前列的水量决定权在左边
// 那么可以计算左指针当前列的水量:左边最大高度-当前列高度
res += leftMax - height[left];
left++;
}else{
// 右边同理
res += rightMax - height[right];
right--;
}
}
return res;
}

滑动窗口

无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。

提示:
0 <= s.length <= 5 * 104

s 由英文字母、数字、符号和空格组成

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

代码:

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
/**
* 计算字符串中最长无重复字符的子串的长度
* 通过维护一个滑动窗口,使用HashSet来记录窗口中的字符,确保无重复
* 当遇到重复字符时,移动窗口的左边界,直到移除该重复字符
* 在每次迭代中更新最长无重复子串的长度
*
* @param s 输入的字符串
* @return 最长无重复字符的子串的长度
*/
public int lengthOfLongestSubstring(String s) {
// 将字符串转换为字符数组,便于逐个字符处理
char[] charArray = s.toCharArray();
// 初始化最长无重复子串的长度为0
int res = 0;
// 使用HashSet存储当前遍历的无重复字符
Set<Character> set = new HashSet<>();
// 初始化滑动窗口的左右指针i和j,从字符串的开始位置出发
for (int i = 0, j = 0; j < charArray.length; j++) {
// 获取当前遍历的字符
char c = charArray[j];
// 当字符已经存在于Set中时,循环移除字符,直到移除重复的字符
while (set.contains(c)) {
set.remove(charArray[i]);
i++;
}
// 将当前字符添加到Set中
set.add(c);
// 更新最长无重复子串的长度
res = Math.max(res, j - i + 1);
}
// 返回最长无重复子串的长度
return res;
}

找到字符串中所有字母异位词

给定两个字符串 s 和 p,找到 s ****中所有 p ****的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
提示:
1 <= s.length, p.length <= 3 * 104

s 和 p 仅包含小写字母

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

代码:

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
46
47
48
49
50
51
52
53
54
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<Integer>();
int slen = s.length();
int plen = p.length();

// 判不合理
if(slen<plen){
return new ArrayList<Integer>();
}

int[] count = new int[26];
// 用起始索引0的情况初始化count数组
for(int i=0;i<plen;i++){
count[s.charAt(i)-'a']++;
count[p.charAt(i)-'a']--;
}

// 初始化differ
int differ=0;
for(int j=0;j<26;j++){
if(count[j]!=0){
differ++;
}
}
// 初始化ans
if(differ==0){
ans.add(0);
}
// 滑动过程,起始索引是i+1
for(int i=0;i<slen-plen;i++){
// 把左端滑出窗口,判断differ变化
count[s.charAt(i)-'a']--;
if(count[s.charAt(i)-'a']==0){
differ--;
}else if(count[s.charAt(i)-'a']==-1){
differ++;
}
// 把右端滑入,判断differ变化
count[s.charAt(i+plen)-'a']++;
if(count[s.charAt(i+plen)-'a']==0){
differ--;
}
else if(count[s.charAt(i+plen)-'a']==1){
differ++;
}

// 符合条件否
if(differ==0){
ans.add(i+1);
}
}
return ans;
}

参考资料