xicheng
2022/10/10阅读：27主题：默认主题
数组-双指针之左右指针（这期长，忍一下）
前言
兄弟们，上篇文章讲了双指针的快慢指针，双指针是数组类算法题中最重要的一个分支之一。这篇文章讲双指针技巧的左右指针技巧。文章很长，几乎涵盖了所有的左右指针技巧，希望大家能耐心看完。另外，数组有下图这些知识点与技巧。
思路
通过条件控制左右指针往中间移动，注意处理好细节，左右指针移动模板如下。
l = 0, r = nums.length - 1;
if (res > target) {
r--;
} else if (res < target) {
l++;
}
两数之和 II - 输入有序数组
解题思路
左右指针。若两数之和大于目标数，右指针-1。若小于目标数，左指针+1。
复杂度分析
时间复杂度：O(n)，n 是数组的长度。
空间复杂度：O(1)。
代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int left = 0, right = numbers.length - 1; left < right; ) {
if (numbers[left] + numbers[right] > target) {
right--;
} else if (numbers[left] + numbers[right] < target){
left++;
} else {
return new int[] {left + 1, right + 1};
}
}
return null;
}
}
最长回文子串
解题思路
左右指针。从数组 i = 0 开始，以此选定中心数字，然后围绕中心数字，计算出最长的回文字串。但选定中心数字 i 后，有两种计算回文的方式。
方式一：将 i - 1 与 i + 1 比较，i - 2 与 i + 2 比较，以此类推。即回文子串的长度为奇数。
方式二：将 i - 1 与 i 比较，i - 2 与 i + 1 比较，以此类推，即回文子串的长度为偶数。
需要注意，上文中给的左右指针模板是从左右两边往中间移动，而该题的思路，是左右指针从中心数字往左右两边移动。
复杂度分析
时间复杂度：O( )，n 是字符串的长度。字符串最多有 n 个中心数字，中心数字最多会向外扩展 n / 2 次。
空间复杂度：O(1)。
代码
class Solution {
public String longestPalindrome(String s) {
String max = "", sub = "";
for (int mid = 0; mid < s.length(); mid++) {
//回文子串的长度为奇数时
sub = maxPalindromeOfMid(s, mid - 1, mid + 1);
max = max.length() > sub.length() ? max : sub;
//回文子串的长度为偶数时
sub = maxPalindromeOfMid(s, mid - 1, mid);
max = max.length() > sub.length() ? max : sub;
}
return max;
}
private String maxPalindromeOfMid(String s, int l, int r) {
//计算回文的数量
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return s.substring(l + 1, r);
}
}
优势洗牌
解题思路
使用田忌赛马的策略，假设 nums1 与 nums2 的长度都是 3。每个元素从小到大依次称为下等马，中等马，上等马。
用 nums1 的上等马与 nums2 的上等马比较，如果有优势（即 num1 中最大的数>nums2 中最大的数），则使用 nums1 的上等马，如果没有优势，则使用 nums1 的剩余的下等马（即 nums1 中未使用过的数中最小的那个）。
这里可能读者会有疑问：如果 nums1 的中等马对 nums2 的上马也有优势。是否需要用 nums1 的中等马对战 nums2 的上等马，达到节约战力的作用呢？
答案是没有必要。如果 nums1 的中等马对 nums2 的上等马有优势，则 nums1 的中等马对 nums2 的中等马也会有优势的。
转换为代码：使用左右指针，先将 nums1，nums2 降序排列，然后左指针指向 num1 中最小的数，右指针指向 num1 中最大的数。
依此从大到小拿出 num2 中的每个数。如果 nums2 中拿出的数比 nums1 的最大数小，则就使用 nums1 的最大数，否则使用 nums1 最小数。
复杂度分析
时间复杂度：O(n)，数组 nums2 长度。
空间复杂度：O(n)。
代码
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
//o[0]是nums2的值，0[1]是nums2的下标
PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
for (int i = 0; i < nums2.length; i++) {
queue.offer(new int[] {nums2[i], i});
}
int[] res = new int[nums1.length];
int l = 0, r = res.length - 1;
while (!queue.isEmpty()) {
int[] item = queue.poll();
int val = item[0], idx = item[1];
//比得过就比
if (nums1[r] > val) {
res[idx] = nums1[r];
r--;
} else {
//比不过就用最小的数去混
res[idx] = nums1[l];
l++;
}
}
return res;
}
}
小于 K 的两数之和
解题思路
-
将 nums 升序排序。 -
初始状态令左指针 l = 0，右指针 r = nums.length - 1。 -
当 nums[l] + nums[r] >= k 时，则左移右指针。 -
当 nums[l] + nums[r] < k 时，则右移左指针，并更新结果 sum。 -
重复 3-4 步，直到 l 不再小于 r 为止。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
代码
class Solution {
public int twoSumLessThanK(int[] nums, int k) {
Arrays.sort(nums);
int l = 0, r = nums.length - 1, sum = -1;
while (l < r) {
int res = nums[l] + nums[r];
if (res < k) {
sum = Math.max(sum, res);
l++;
} else {
r--;
}
}
return sum;
}
}
较小的三数之和
解题思路
使用左右指针技巧，例如 nums = [0, 1, 2, 3, 4]。
-
将 nums 数组升序排序。 -
外层循环，将 i 从 0 开始，直到 i 不再小于 nums.length - 2。为什么是 nums.length - 2，下文会讲。 -
在数组中 i 的右侧位置，嵌套内层循环，内层循环使用左右指针（因为 i 的右侧有左右指针，至少会占两个位置，所以 i 最 4. 多到 nums.length - 3），令 l = i + 1，r = nums.length - 1。 -
当 nums[i] + nums[l] + nums[r] >= target 时，则将 r 指针左移动一位。 -
当 nums[i] + nums[l] + nums[r] < target 时，r - l 的值就是在当前 l 的取值下满足题意的三元组的个数。再将 l 指针右移动一位。 -
重复 4.5 步，直到 l 不再小于 r 为止。 -
i 右移动一位，重复 3-6 步，直到 i 不再小于 nums.length - 2 为止。
复杂度分析
时间复杂度：O( )。内层的双指针循环复杂度为 O(n)，再加上外层循环，所以复杂度为 O( )。
空间复杂度：O(1)。
代码
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1, r = nums.length - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] < target) {
count += r - l;
l++;
} else {
r--;
}
}
}
return count;
}
}
最接近的三数之和
解题思路
使用左右指针技巧，与《259.较小的三数之和》类似。例如 nums = [0, 1, 2, 3, 4]。
-
将 nums 数组升序排序。 -
外层循环，将 i 从 0 开始遍历，直到 i 不再小于 nums.length - 2。 -
在数组中 i 的右侧位置，嵌套内层循环，内层循环使用左右指针（因为 i 的右侧有左右指针，至少会占两个位置，所以 i 最多到 nums.length - 3），令左指针 l = i + 1，右指针 r = nums.length - 1。 -
计算 res = nums[i] + nums[l] + nums[r]。若 res - target 的绝对值比上次 res - target 的绝对值小，即这次的三个数和更接近 target，则记录下当前 res。 -
当 res > target 时，则将 r 指针左移动一位。 -
当 res < target 时，则再将 l 指针右移动一位。 -
当 res = target 时，直接返回 res。 -
重复 4-7 步，直到 l 不再小于 r 为止。 -
i 右移动一位，重复 3-8 步，直到 i 不再小于 nums.length - 2 为止。
复杂度分析
时间复杂度：O( )。内层的双指针循环复杂度为 O(n)，再加上外层循环，所以复杂度为 O( )。
空间复杂度：O(1)。
代码
class Solution {
public int twoSumLessThanK(int[] nums, int k) {
Arrays.sort(nums);
int l = 0, r = nums.length - 1, sum = -1;
while (l < r) {
int res = nums[l] + nums[r];
if (res < k) {
sum = Math.max(sum, res);
l++;
} else {
r--;
}
}
return sum;
}
}
三数之和
解题思路
想要求三数和，首先用左右指针求两数和，注意结果集记得去重。
拓展：若要求 n 数和，则先求 n - 1 数和。若想求 n - 1 数和，则先求 n - 2 数和，依此类推，一开始先用左右指针求两数和。
复杂度分析
时间复杂度：O( )，左右指针计算两数和的复杂度是 O(n)，再加上左右指针的外层循环，也就是确定第三个数的循环的复杂度时 O(n)，因此为 O( )。
空间复杂度：O( )。需要中间变量存储递归返回的结果即排列中的 。
代码
该代码是 n 数和的模板代码，《18.四数之和》可以用该模板。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
return nSum(nums, 3, 0, 0);
}
private List<List<Integer>> nSum(int[] nums, int n, int start, int sum) {
int len = nums.length;
if (len < 2 || n > len) {
return new ArrayList<>();
}
if (n == 2) {
return sumTwo(nums, start, sum);
}
int lastNum = Integer.MIN_VALUE;
List<List<Integer>> list = new ArrayList<>();
for (int i = start; i < len - 2; i++) {
//i右移后值还是与右移前相等，则继续右移
if (lastNum == nums[i]) {
continue;
}
lastNum = nums[i];
//和为sum - nums[i]的n - 1数和的数组下标
List<List<Integer>> res = nSum(nums, n - 1, i + 1, sum - nums[i]);
for (List<Integer> item : res) {
item.add(nums[i]);
//添加到结果集
list.add(item);
}
}
return list;
}
private List<List<Integer>> sumTwo(int[] nums, int start, int sum) {
List<List<Integer>> list = new ArrayList<>();
int l = start, r = nums.length - 1;
while (l < r) {
int twoSum = nums[l] + nums[r];
int left = nums[l], right = nums[r];
//两数和小于目标值，左指针右移
if (twoSum < sum) {
//右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
while (l < r && left == nums[l]) {
l++;
}
}
//两数和大于目标值，左指针右移
else if (twoSum > sum) {
//右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
while (l < r && right == nums[r]) {
r--;
}
}
//两数和等于目标值
else {
list.add(new ArrayList<>(Arrays.asList(nums[l], nums[r])));
//右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
while (l < r && left == nums[l]) {
l++;
}
//右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
while (l < r && right == nums[r]) {
r--;
}
}
}
return list;
}
}
四数之和
解题思路
想要求三数和，首先用左右指针求两数和，注意结果集记得去重。
拓展：若要求 n 数和，则先求 n - 1 数和。若想求 n - 1 数和，则先求 n - 2 数和，依此类推，一开始先用左右指针求两数和。
参考《三数之和》的模板代码
复杂度分析
时间复杂度：O( )，左右指针计算两数和的复杂度是 O(n),除了左右指针外，剩余两个数，每个数有一个循环，分别都为 O(n)，因此为 O( )。
空间复杂度：O( )。需要中间变量存储递归返回的结果即排列中的 。
代码
套用 n 数和的模板。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return nSum(nums, 4, 0, target);
}
private List<List<Integer>> nSum(int[] nums, int n, int start, int sum) {
int len = nums.length;
if (len < 2 || n > len) {
return new ArrayList<>();
}
if (n == 2) {
return sumTwo(nums, start, sum);
}
int lastNum = Integer.MIN_VALUE;
List<List<Integer>> list = new ArrayList<>();
for (int i = start; i < len - 2; i++) {
//i右移后值还是与右移前相等，则继续右移
if (lastNum == nums[i]) {
continue;
}
lastNum = nums[i];
//和为sum - nums[i]的n - 1数和的数组下标
List<List<Integer>> res = nSum(nums, n - 1, i + 1, sum - nums[i]);
for (List<Integer> item : res) {
item.add(nums[i]);
//添加到结果集
list.add(item);
}
}
return list;
}
private List<List<Integer>> sumTwo(int[] nums, int start, int sum) {
List<List<Integer>> list = new ArrayList<>();
int l = start, r = nums.length - 1;
while (l < r) {
int twoSum = nums[l] + nums[r];
int left = nums[l], right = nums[r];
//两数和小于目标值，左指针右移
if (twoSum < sum) {
//右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
while (l < r && left == nums[l]) {
l++;
}
}
//两数和大于目标值，左指针右移
else if (twoSum > sum) {
//右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
while (l < r && right == nums[r]) {
r--;
}
}
//两数和等于目标值
else {
list.add(new ArrayList<>(Arrays.asList(nums[l], nums[r])));
//右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
while (l < r && left == nums[l]) {
l++;
}
//右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
while (l < r && right == nums[r]) {
r--;
}
}
}
return list;
}
}
盛最多水的容器
解题思路
该题仍然采用左右指针思路，每次向中间移动左右两块柱子中较矮的那一根，并记录容纳水的最大值。
具体步骤：
-
双指针 l , r 指向水槽的两端。 -
哪个指针指向的元素小，就往中间移动，相同时任意往中间移动一个指针并更新容纳水的最大值。 -
直到 l 不再小于 r 位置，并返回容纳水的最大值。 上述思路的正确性证明： 令左指针=l，右指针=r，左右指针的距离为 w，则面积 S(l, r) = min(h[l], h[r]) * w。
当 h[l] < h[r]时，l++。会丢失掉 S(l, l + 1), S(l, l + 2), ..., S(l, r - 1)这几种可能， 统称为 S(l, r') = min(h[l], h[r']) * w'。
又因为 h[l] < h[r]，所以 h[l]<h[r']时 min(h[l], h[r']) = h(l)，h[l]>h[r']时 min(h[l], h[r'])=h[r'].所以 min(h[l], h[r']) <=min(h[l], h[r])。
又因为 w' < w。所以 min(h[l], h[r']) _ w' < min(h[l], h[r]) _ w，所以 S(l,r') < S(l, r)。
所以左指针右移后丢掉的几种可能的面积中，都比右移前的面积小。
同理可得出 h[l] > h[r]时，r--，丢掉的几种可能的面积中，都比移动前更小。
进一步得出：h[l] = h[r]时，可以任意移动左指针或者右指针。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
代码
class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1, max = Math.min(height[l], height[r]) * (r - l);
while (l < r) {
if (height[l] <= height[r]) {
l++;
} else {
r--;
}
int area = Math.min(height[l], height[r]) * (r - l);
max = Math.max(area, max);
}
return max;
}
}
接雨水
解题思路
采用左右指针思路，该题非常巧妙简洁：
移动左指针时，左指针最新指向的柱子上方能接的水，为该柱子左指针右移时扫过部分（除开最新指向的那一根柱子）中最高的那根 A，与右指针左移扫过部分中最高的那根 B 中较矮的那一根，与当前柱子的差值。
移动右指针时，右指针最新指向的柱子上方能接的水，为左指针右移扫过部分中最高的那根 A，与柱子右指针左移扫过部分中最高的那根 B（除开右指针最新指向的那个柱子）中较矮的那一根，与当前柱子的差值。
具体步骤：
-
双指针 l , r 分别指向 0，height.length - 1。左指针扫过 lMax=heigth[0]，右边最高的柱子为 rMax = heigth[height.length - 1]。 -
如果 l 指向的柱子更低，即 height[l] < height[r]。右移左指针，即 l++。此时 l 指向的柱子的左边最高的柱子的高度就是 lMax，l 指向的柱子的右边，且 r 指针扫过的柱子中，最高的柱子的高度就是 rMax。当前柱子上方能接的水就是 ans = min(lMax, rMax) - 当前柱子高度。注意若 ans <0，该柱子上方就不能接水。此时比较 lMax 与 l 所指向的柱子的高度，谁高就将谁赋值给 lMax。 -
如果 r 指向的柱子更低或者二者相同，根据第 2 步来镜像处理。 -
重复 2-3 步，直到 l 不再小于 r 为止，统计每根柱子上方能接的雨水。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
代码
class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1, sum = 0, lMax = height[l], rMax = height[r];
while (l < r) {
int minHeight = Math.min(lMax, rMax);
if (height[l] < height[r]) {
l++;
sum += Math.max(0, minHeight - height[l]);
lMax = Math.max(lMax, height[l]);
} else {
r--;
sum += Math.max(0, minHeight - height[r]);
rMax = Math.max(rMax, height[r]);
}
}
return sum;
}
}
结尾
恭喜你已经掌握了双指针之左右指针，下篇算法文章讲双指针的滑动窗口。
微信扫描下方二维码，或搜索“xicheng”，关注公众号后回复【笔记】，有我准备的 15 万字 Java 面试笔记。
感谢各位人才的点赞、收藏和评论，干货文章持续更新中，下篇文章再见！
作者介绍