🎯 LeetCode Hot 100
283. 移动零
难度：简单 | LeetCode 链接
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
1
2
| 输入: nums = [0,1,0,3,12]
输出: [1,3,12,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
| class Solution {
public void moveZeroes(int[] nums) {
int length = nums.length;
for(int left=0;left<length;left++){
if(nums[left] == 0){
int right = left+1;
while(right<length&&nums[right]==0){
right++;
}
if(right>=length){
return;
}
int tmp = nums[right];
nums[right] = nums[left];
nums[left] = tmp;
}
}
}
}
|
复杂度：时间 O(n)，空间 O(1)
11. 盛最多水的容器
难度：中等 | LeetCode 链接
给定 n 个非负整数 height，每个数代表坐标中的一个点 (i, height[i])。找出两条线，使得它们与 x 轴构成的容器可以容纳最多的水。
1
2
3
| 输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：选择 height[1]=8 和 height[8]=7，宽度为 7，面积 = 7 × 7 = 49
|
思路
双指针从两端向中间收缩，每次移动较短的那条边。
为什么移动短边？
- 面积 =
min(左高, 右高) × 宽度
- 宽度一定减小，要想面积可能变大，只能让高度变大
- 移动长边：
min 值不变或变小，面积一定变小
- 移动短边：
min 值可能变大，面积可能变大
- 把左右指针看成x,y轴，图中是所有的组合，直接排除短边i=0，可以跳过i=0和j=1~8的组合，以此类推。
- 利用空间缩减的思想：移动短边并不会漏掉最优解，目的是可以跳过一些不必要的计算。
- 详解见LeetCode
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int maxArea(int[] height) {
int l = 0,r = height.length-1;
int res = 0;
while(l<r){
int area = (r-l)*Math.min(height[l],height[r]);
res = Math.max(res,area);
if(height[l]<height[r]){
l++;
}else{
r--;
}
}
return res;
}
}
|
复杂度：时间 O(n)，空间 O(1)
15. 三数之和
难度：中等 | LeetCode 链接
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c ，使得 a + b + c = 0。找出所有满足条件且不重复的三元组。
1
2
| 输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
|
思路
先排序。固定一个数 i，对剩余区间用双指针 l/r 夹逼，按和的大小移动指针。注意跳过重复值
代码
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i<nums.length;i++){
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int target = -nums[i];
int l = i+1,r=nums.length -1;
while(l<r){
if(nums[l]+nums[r] == target){
res.add(Arrays.asList(nums[i],nums[l],nums[r]));
l++;
r--;
while(nums[l-1]==nums[l]&&l<r){
l++;
}
while(nums[r+1]==nums[r]&&l<r){
r--;
}
continue;
}
if(nums[l]+nums[r] < target){
l++;
continue;
}
if(nums[l]+nums[r] > target){
r--;
}
}
}
return res;
}
}
|
复杂度：时间 O(n²)，空间 O(1)
42. 接雨水
难度：困难 | LeetCode 链接
给定 n 个非负整数表示每个柱子的高度图，宽度均为 1，计算下雨之后能接多少雨水。
1
2
| 输入：height = [4,2,0,3,2,5]
输出：9
|
思路
双指针分别从两端向中间移动，并维护当前位置左侧/右侧的最高高度 leftMax 和 rightMax。当前列可以接的水量由更矮一侧的最高高度决定，因此移动较低的一侧指针并累加水量，整体只需一次遍历。
代码
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
| class Solution {
public int trap(int[] height) {
int preMax[] = new int[height.length];
preMax[0] = height[0];
for(int i=1;i<height.length;i++){
preMax[i] = Math.max(preMax[i-1],height[i]);
}
int sufMax[] = new int[height.length];
sufMax[height.length-1] = height[height.length-1];
for(int i=height.length-2;i>=0;i--){
sufMax[i] = Math.max(sufMax[i+1],height[i]);
}
int ans = 0;
for(int i=0;i<height.length;i++){
ans += Math.min(preMax[i],sufMax[i]) - height[i];
}
return ans;
}
}
|
复杂度：时间 O(n)，空间 O(n) 或 O(1)