关于双指针算法问题的思考
大家好，我是 方圆。本篇是对双指针算法的总结，我将它分成了数组和字符串类型的题目，大家可以按照文章题目的顺序进行练习，如果大家想要找刷题路线的话，可以参考 Github: LeetCode。
数组
两端指针
如果两指针定义在数组两端，并且两指针不断地向对方靠近，那么判断循环的条件如下：
while(left <[=] right) {
// ... do something
}
其中等号条件是可选的，我们可以通过长度为 1 的数组判断是否需要添加等号：
-
若长度为 1 的数组也需要执行相关处理逻辑，那么需要等号；
-
若长度为 1 的数组不需要执行相关处理逻辑，那么不需要等号
相关练习如下：
本题是简单题目，定义双指针在数组的两端，交换奇数和偶数的位置即可，题解如下：
public int[] trainingPlan(int[] actions) {
int left = 0, right = actions.length - 1;
while (left < right) {
while (left < right && actions[left] % 2 == 1) {
left++;
}
while (left < right && actions[right] % 2 == 0) {
right--;
}
swap(actions, left, right);
}
return actions;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
本题比较简单，将原数组排序后找到与排序前左右两端第一个数值不同的位置即可，题解如下：
public int findUnsortedSubarray(int[] nums) {
int[] temp = new int[nums.length];
System.arraycopy(nums, 0, temp, 0, temp.length);
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
while (left <= right && nums[left] == temp[left]) {
left++;
}
while (left <= right && nums[right] == temp[right]) {
right--;
}
return right - left + 1;
}
本题指针变换的规则是高度较小的指针向另一个指针靠近，以尝试取得更高的高度，题解如下，需要注意 (right - left) * height[left++] 代码的顺序，不能写成 height[left++] * (right - left) ，否则它会先移动指针再计算面积，使得答案偏小：
public int maxArea(int[] height) {
int res = 0;
int left = 0, right = height.length - 1;
while (left < right) {
if (height[left] <= height[right]) {
res = Math.max((right - left) * height[left++], res);
} else {
res = Math.max((right - left) * height[right--], res);
}
}
return res;
}
本题指针变换的规则是在满足每艘船最多装两个人的前提下，先不断地装较大重量的人，之后再尝试能不能装小重量的人，这样使得两指针不断向对方靠近，即使 people[] 数组中只有一个人坐船，仍然需要一条船来装载他，所以 while 循环条件需要等号，题解如下：
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int res = 0;
int left = 0, right = people.length - 1;
while (left <= right) {
int weight = 0;
int peopleNum = 0;
while (left <= right && weight + people[right] <= limit && peopleNum < 2) {
peopleNum++;
weight += people[right--];
}
while (left <= right && weight + people[left] <= limit && peopleNum < 2) {
peopleNum++;
weight += people[left++];
}
res++;
}
return res;
}
本题是模拟结合双指针的应用，和 田忌赛马 的思路一致，即排序后按顺序用 nums1[] 牌组中较小的牌来对应 nums2[] 牌组中较大的牌，其余的牌按照大于等于的规则去对应。我们使用 HashMap 来记录排序前 nums2 的索引位置，因为有重复的牌所以需要使用 LinkedList 来保存多个索引。长度为 1 的牌组也需要进行洗牌，所以 while 循环条件需要等号，题解如下：
public int[] advantageCount(int[] nums1, int[] nums2) {
HashMap<Integer, LinkedList<Integer>> numIndex = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
LinkedList<Integer> index = numIndex.getOrDefault(nums2[i], new LinkedList<>());
index.add(i);
numIndex.put(nums2[i], index);
}
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] res = new int[nums1.length];
// 排序后 nums1 中需要拿出来的牌的索引位置
int n = 0;
int left = 0, right = nums2.length - 1;
while (left <= right) {
if (nums1[n] <= nums2[left]) {
res[numIndex.get(nums2[right--]).pollFirst()] = nums1[n++];
} else {
res[numIndex.get(nums2[left++]).pollFirst()] = nums1[n++];
}
}
return res;
}
双指针起点在同一位置
本题需要找到数组中所有不同的元素，思路是 left 和 right 指针都在数组最左端，使用 left 指针来记录不同元素的索引位置，right 指针则负责查找在数组中不同的元素，题解如下：
public int removeDuplicates(int[] nums) {
int left = 0, right = 0;
while (right < nums.length) {
while (right + 1 < nums.length && nums[right] == nums[right + 1]) {
right++;
}
if (right < nums.length) {
nums[left++] = nums[right++];
}
}
return left + 1;
}
本题和上一题思路基本一致，不再赘述，题解如下：
public int removeElement(int[] nums, int val) {
int left = 0, right = 0;
while (right < nums.length) {
while (right < nums.length && nums[right] == val) {
right++;
}
if (right < nums.length) {
nums[left++] = nums[right++];
}
}
return left;
}
本题需要结合二分查找来求解，如果查找到的索引位置为右端点或者存在小于 x 的数相比于二分查找的结果更接近 x，那么需要将 left 执行减 1 操作，随后我们将 right 指针也移动到 left 指针的位置，这表示第一个符合条件的数字，之后两指针向左向右扩张，根据不超过 k 长度的条件找到合适的区间范围，最后再将区间内的值封装到 list 内即可，题解如下：
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.length;
while (left < right) {
int mid = left + right >> 1;
if (arr[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
if (left == arr.length || (left > 0 && check(arr[left - 1], arr[left], x))) {
left--;
}
right = left;
while (right - left + 1 < k) {
if (left - 1 >= 0 && right + 1 < arr.length && check(arr[left - 1], arr[right + 1], x)) {
left--;
} else if (left - 1 >= 0 && right + 1 < arr.length && check(arr[right + 1], arr[left - 1], x)) {
right++;
} else if (left - 1 >= 0) {
left--;
} else {
right++;
}
}
List<Integer> res = new ArrayList<>(k);
for (int i = 0; i < k; i++) {
res.add(arr[left++]);
}
return res;
}
private boolean check(int a, int b, int x) {
return Math.abs(a - x) < Math.abs(b - x) || (Math.abs(a - x) == Math.abs(b - x) && a < b);
}
本题的思路是：确定别人给自己发送好友请求的范围下界 left，即同龄的人们，和别人给自己发送好友请求的范围上界 right，即题目要求的年龄范围，最终 [left, right] 区间长度 - 1 即为发送好友请求的次数，需要注意 right 指针每次开始匹配的位置要从当前的索引开始，否则可能会发生 left 指针超过 right 指针的情况，题解如下：
public int numFriendRequests(int[] ages) {
Arrays.sort(ages);
int res = 0;
int left = 0, right = 0;
for (int i = 0; i < ages.length; i++) {
while (left < i && noSend(ages[left], ages[i])) {
left++;
}
if (right < i) {
right = i;
}
while (right + 1 < ages.length && !noSend(ages[right + 1], ages[i])) {
right++;
}
res += right - left;
}
return res;
}
public boolean noSend(int x, int y) {
return y <= 0.5 * x + 7 || y > x;
}
和“滑动窗口”有点儿像
该类型下的题目我觉得很有意思，起初我觉得它们和滑动窗口类型的题目很像，在满足条件的情况下 right 指针不断地向右滑动，类似求满足条件的最大窗口，但是我并没有将它们归类在滑动窗口类型题目下，因为它们每次滑动开始都需要将左端 left 固定，之后在满足条件的情况下将窗口不断扩大，并且每次 right 滑动到极限， left 指针需要直接“跳跃到” right 指针的位置，而不是一步步地移动（left++），所以还是将它们归类在双指针下，以做辨别和区分。
本题指针变换的规则是在当前区间上界大于等于下一个区间的下界时，right 指针右移，统计完当前最大的区间范围后，left 和 right 指针一同在新的索引处，代码如下：
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));
ArrayList<int[]> res = new ArrayList<>();
int left = 0, right = 0;
while (right < intervals.length) {
int l = intervals[left][0];
int r = intervals[left][1];
while (right + 1 < intervals.length && r >= intervals[right + 1][0]) {
r = Math.max(r, intervals[++right][1]);
}
res.add(new int[]{l, r});
left = ++right;
}
return res.toArray(new int[0][]);
}
本题需要判断公差是否相等，定义双指针为 int left = 0, right = left + 1; ，指针变换的规则是在满足等差数列的情况下不断右移 right 指针，right 指针始终表示有效区间范围内的上界，统计完该区间范围内有效的子数组之后，left 指针移动到 right 指针位置，right 指针再移动到 left 指针的后一位，保证能计算公差。除此之外需要注意，在计算符合条件的答案时，要满足区间长度大于等于 3，所以子数组数目等于当前区间的所有子数组的数量减 2，即 right - left - 1，题解如下：
public int numberOfArithmeticSlices(int[] nums) {
int res = 0;
if (nums.length < 3) {
return res;
}
int left = 0, right = left + 1;
while (right < nums.length) {
int b = nums[right] - nums[left];
while (right + 1 < nums.length && (nums[right + 1] - nums[right]) == b) {
right++;
if (right - left + 1 >= 3) {
res += right - left - 1;
}
}
left = right++;
}
return res;
}
字符串
两端指针
本题是简单题目，注意使用 Character.isLetterOrDigit() 判断字符是字母还是数字即可，题解如下：
public boolean isPalindrome(String s) {
String lowerCase = s.toLowerCase();
int left = 0, right = lowerCase.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(right))) {
right--;
}
if (lowerCase.charAt(left) != lowerCase.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
双指针起点在同一端
本题的思路比较简单，即找到对应单词的索引位置后计算距离即可：
public int findClosest(String[] words, String word1, String word2) {
int res = words.length;
int word1Index = -1, word2Index = -1;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
word1Index = i;
}
if (words[i].equals(word2)) {
word2Index = i;
}
if (word1Index != -1 && word2Index != -1) {
res = Math.min(res, Math.abs(word1Index - word2Index));
}
}
return res;
}
本题需要认真的读题理解题意，根据扩张的条件编写 isStretchy 方法，随后逐个的判断字母组是否能扩张成 s，题解如下：
public int expressiveWords(String s, String[] words) {
int res = 0;
for (String word : words) {
if (isStretchy(s, word)) {
res++;
}
}
return res;
}
private boolean isStretchy(String origin, String word) {
int originBegin = 0, originEnd = 0;
int wordBegin = 0, wordEnd = 0;
while (originEnd < origin.length() && wordEnd < word.length()) {
if (origin.charAt(originEnd) != word.charAt(wordEnd)) {
return false;
}
while (originEnd + 1 < origin.length() && origin.charAt(originEnd) == origin.charAt(originEnd + 1)) {
originEnd++;
}
while (wordEnd + 1 < word.length() && word.charAt(wordEnd) == word.charAt(wordEnd + 1)) {
wordEnd++;
}
if (wordEnd - wordBegin > originEnd - originBegin) {
return false;
}
if (wordEnd - wordBegin < originEnd - originBegin && originEnd - originBegin + 1 < 3) {
return false;
}
originBegin = ++originEnd;
wordBegin = ++wordEnd;
}
return originEnd == origin.length() && wordEnd == word.length();
}
本题需要先将 dictionary 按照字符长度和字母序排序，之后采用双指针来判断其中元素是否能完成匹配，第一个匹配完成的即为长度最长且字母序最小的字符串，题解如下：
public String findLongestWord(String s, List<String> dictionary) {
dictionary.sort((x, y) -> {
if (x.length() != y.length()) {
return y.length() - x.length();
}
return x.compareTo(y);
});
String res = "";
for (String d : dictionary) {
int dIndex = 0, sIndex = 0;
while (dIndex < d.length() && sIndex < s.length()) {
if (d.charAt(dIndex) != s.charAt(sIndex)) {
sIndex++;
continue;
}
dIndex++;
sIndex++;
}
if (dIndex == d.length()) {
res = d;
break;
}
}
return res;
}
使用 right 指针确定当前字符的最大上界，如果区间长度大于 1 的话，那么将区间长度数字转换成字符串，并将字符从高位拼接到低位即可：
public int compress(char[] chars) {
int index = 0;
int left = 0, right = 0;
while (right < chars.length) {
while (right + 1 < chars.length && chars[right + 1] == chars[right]) {
right++;
}
chars[index++] = chars[right];
if (right - left > 0) {
char[] num = String.valueOf(right - left + 1).toCharArray();
for (char c : num) {
chars[index++] = c;
}
}
left = ++right;
}
return index;
}
推多米诺的解题思路是确定字符 . 左右两边的多米诺骨牌的倒向来判断当前位置的倒向，题解如下：
public String pushDominoes(String dominoes) {
char[] charArray = dominoes.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if (charArray[i] == '.') {
int left = i - 1, right = i + 1;
while (right < charArray.length && charArray[right] == '.') {
right++;
}
i = right;
char leftChar = left == -1 ? 'L' : charArray[left];
char rightChar = right == charArray.length ? 'R' : charArray[right];
left++; right--;
if (leftChar == 'R' && rightChar == 'L') {
while (left < right) {
charArray[left++] = 'R';
charArray[right--] = 'L';
}
} else if (leftChar == 'R' && rightChar == 'R') {
while (left <= right) {
charArray[left++] = 'R';
}
} else if (leftChar == 'L' && rightChar == 'L') {
while (left <= right) {
charArray[left++] = 'L';
}
}
}
}
return new String(charArray);
}
如果字符是 X 的话，那么指针向右移动；非 X 时，如果两字符不等的话，那么不能完成转换；如果两字符均为 R，只有 sIndex 小于 eIndex 时才能转换；如果两字符均为 L，只有 sIndex 大于 eIndex 时才能转换，题解如下：
public boolean canTransform(String start, String end) {
int sIndex = 0, eIndex = 0;
while (sIndex < start.length() || eIndex < end.length()) {
while (sIndex < start.length() && start.charAt(sIndex) == 'X') {
sIndex++;
}
while (eIndex < end.length() && end.charAt(eIndex) == 'X') {
eIndex++;
}
if (sIndex == start.length() || eIndex == end.length()) {
return sIndex == eIndex;
}
if (start.charAt(sIndex) != end.charAt(eIndex)) {
return false;
}
if (start.charAt(sIndex) == 'R' && sIndex > eIndex) {
return false;
}
if (start.charAt(sIndex) == 'L' && sIndex < eIndex) {
return false;
}
sIndex++;
eIndex++;
}
return true;
}
本题思路相对来说不是很好想，我们一起看一下。首先我们将 first 始终定义为较长的字符串，如果两字符串长度差大于 1 则删除字符的次数大于 1，那么不符合条件。之后接着判断，如果指针处字符相同的话，那么两个指针一起向右移动；如果指针处字符不同，则需要确定是删除字符还是替换字符：first 字符串长的话，那么选择删除字符的策略，因为最终两字符串编辑完一定是等长的，否则选择替换字符的策略，题解如下：
public boolean oneEditAway(String first, String second) {
if (first.length() < second.length()) {
String temp = first;
first = second;
second = temp;
}
if (first.length() - second.length() > 1) {
return false;
}
int fIndex = 0, sIndex = 0;
int count = 0;
while (fIndex < first.length() && sIndex < second.length()) {
if (first.charAt(fIndex) == second.charAt(sIndex)) {
fIndex++;
sIndex++;
} else {
// 不等长选择删除策略，等长选择替换策略
if (first.length() - fIndex > second.length() - sIndex) {
fIndex++;
} else {
fIndex++;
sIndex++;
}
count++;
}
}
return count <= 1;
}
模拟
本题发现规律后比较容易，在数字长度小于等于 3 时，1 的数目为 1，数字长度大于 3 之后需要根据 index 处的值递推出索引 i 处的值，题解如下：
public int magicalString(int n) {
// 1221121221221121122...
if (n <= 3) {
return 1;
}
int index = 2;
int[] nums = new int[n + 2];
nums[0] = 1;
nums[1] = 2;
nums[2] = 2;
int num = 1;
for (int i = 3; i < n;) {
nums[i++] = num;
if (nums[index] == 2) {
nums[i++] = num;
}
if (num == 1) {
num = 2;
} else {
num = 1;
}
index++;
}
int res = 0;
for (int i = 0; i < n; i++) {
res += nums[i] == 1 ? 1 : 0;
}
return res;
}
加油儿