LeetCode 热题 100 | 双指针
双指针基础
- 通过两个指针在一个for循环下完成两个for循环的工作。能够有效降低多层for循环中一个循环的时间复杂度。
- 双指针求和需要先排序数组，不然不知道该移动哪个指针。
283. 移动零
题目讲解：LeetCode
重点：
- 左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
思路：
- 两个指针，左指针指向已经处理好的序列尾部，右指针指向待处理序列的头部。遍历数组，如果右指针的元素不为0，则与左指针指向的0交换。整个数组没有0也只会与自己交换直到发现第一个0右指针才会比左指针快。
复杂度：
- n 为数组长度。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
public void moveZeroes(int[] nums) {
int left = 0, right = 0;
while (right < nums.length) {
// 重点: 不等于0时是两个指针同步移动
// 等于0时只移动right来寻找下一个非0
if (nums[right] != 0) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
}
right++;
}
}
11. 盛最多水的容器
题目讲解：LeetCode
重点：
- 左指针指向容器左边界，右指针指向容器右边界。
思路：
- 两个指针，左指针指向容器左边界，右指针指向容器右边界。每次移动高度较低的指针。
- 如果移动高的那一边，会有两种情况：
1.下一根柱子的高度比现在高，高度还取最小值低的那边，最大水量比原来小。
2.下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小。- 如果移动低的那一边，会有两种情况：
1.下一根柱子的高度比现在高，高度就可以取更高的值，最大水量不一定比原来小。
2.下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小。复杂度：
- N 是数组长度。
- 时间复杂度：O(N)
- 空间复杂度：O(1)
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int result = 0;
while (left < right) {
int water = (right - left) * Math.min(height[left], height[right]);
result = Math.max(water, result);
// 重点: 每次都只移动较矮的
if (height[left] > height[right]) right--;
else left++;
}
return result;
}
15. 三数之和
题目讲解：LeetCode
重点：
- 双指针。先从小到大排序数组，然后固定一个数使用双指针往中间靠拢即可。根据和的大小来判断该移动左指针还是右指针。
思路：
- 从小到大排序数组。
- 固定一个数，如果该数和上一个数相同，则已经探索过该数，跳过。
- 左指针在i + 1，右指针在nums.length - 1。如果和小于0，左指针加1。如果和大于0，右指针减1。如果和为0，则把left和right移动到不重复的元素上，方便接着探索其他组合。
复杂度：
- N 是数组长度
- 时间复杂度：O(N^2)
- 空间复杂度：O(N)
public List<List<Integer>> threeSum(int[] nums) {
// 重点: 双指针需要排序数组
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
// 重点: 固定a, 根据和的大小来移动b和c
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) return result;
if (i >= 1 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left + 1] == nums[left]) left++;
while (left < right && nums[right - 1] == nums[right]) right--;
left++;
right--;
}
}
}
return result;
}
42. 接雨水
题目讲解：LeetCode
重点：
- 一列一列的计算水。
- 动态规划可以提前计算好每列左和右的最高值。
- 双指针可以实时计算左和右指针的左边最高值和右边最高值。
思路：
- 动态规划：
- 利用动态规划先计算每列左和右的最高高度
- 再遍历每列，根据最高高度计算当前列的雨水。
- 双指针：
- 两个指针，一个指针在开头，一个指针在末尾。leftMax和rightMax分别记录最大值。
- 当出现凹槽的时候：
如果是left出现的凹槽，用leftMax减即可，因为left的右手边最大值肯定大于等于rightMax，我们本意是要取leftMax和rightMax的最小值来计算left这一列的water。
如果是right出现的凹槽，用rightMax减即可，因为right的左手边最大值肯定大于等于leftMax，我们本意是要取leftMax和rightMax的最小值来计算right这一列的water。复杂度：
- N 是数组长度
- 动态规划：
时间复杂度：O(n)
空间复杂度：O(n)- 双指针：
时间复杂度：O(n)
空间复杂度：O(1)
public int trap(int[] height) {
// 重点: 动态规划提前计算好每列左和右的最高高度
int[] maxLeft = new int[height.length];
maxLeft[0] = height[0];
for (int i = 1; i < height.length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
int[] maxRight = new int[height.length];
maxRight[height.length - 1] = height[height.length - 1];
for(int i = height.length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i + 1]);
int result = 0;
for (int i = 0; i < height.length; i++) {
int colWater = Math.min(maxLeft[i], maxRight[i]) - height[i];
result += colWater;
}
return result;
}
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int result = 0;
// 重点: 两个指针往中间靠拢
// 那么leftMax是left左边最高的, rightMax是right右边最高的
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// 重点: 出现凹槽了
// 如果是左矮与右, left的右手边最高值肯定大于等于rightMax, 因为right是右往左遍历, 肯定是能接住leftMax的
// 而left右手边出现更矮的柱子也不妨碍这一列water的计算
// 如果是右矮与左, right的左手边最高值肯定大于等于leftMax, 因为left是左往右遍历, 肯定是能接住rightMax的
// 而right左手边出现更矮的柱子也不妨碍这一列water的计算
if (height[left] < height[right]) {
result += leftMax - height[left];
left++;
} else {
result += rightMax - height[right];
right--;
}
}
return result;
}