LeetCode 热题 100 | 双指针

双指针基础

• 通过两个指针在一个for循环下完成两个for循环的工作。能够有效降低多层for循环中一个循环的时间复杂度。

283. 移动零

题目讲解：LeetCode
重点：

1. 左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

思路：

1. 两个指针，左指针指向已经处理好的序列尾部，右指针指向待处理序列的头部。遍历数组，如果右指针的元素不为0，则与左指针指向的0交换。整个数组没有0也只会与自己交换直到发现第一个0右指针才会比左指针快。

复杂度：

• n 为数组长度。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

public void moveZeroes(int[] nums) {int left = 0, right = 0;while (right < nums.length) {if (nums[right] != 0) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;}right++;}
}

11. 盛最多水的容器

题目讲解：LeetCode
重点：

1. 左指针指向容器左边界，右指针指向容器右边界。

思路：

1. 两个指针，左指针指向容器左边界，右指针指向容器右边界。每次移动高度较低的指针。

• 如果移动高的那一边，会有两种情况：
  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;
}

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：