双指针基础
- 通过两个指针在一个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来寻找下一个非0if (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和cfor (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;
}
