双指针问题
前言 ：众所周知，力扣刷题是有策略的，一个有效的办法是按类刷，并总结该类题目特点，本文是作者在刷题过程中总结的心得，希望能对大家有帮助。
如果有朋友喜欢，后续会上传其他类型的板块，如动态规划~
1. 有序数组的 Two Sum
题解：
对于有序数组，可以使用双指针从两侧开始求和搜索，进行如下判断：
- 左指针与右指针对应的值相加等于目标值，直接返回对应下标；
- 小于目标值，说明左指针应该向右移动；
- 大于目标值，说明右指针应该向左移动；】
注意点：①：根据题目条件，返回数组下标应该加1；
②：数组的值在1000范围内，故numbers[left]+numbers[right] > target成立，否则应该使用减法判断！
class Solution {
public int[] twoSum(int[] numbers, int target) {
int len = numbers.length;
int left = 0,right = len - 1;
while(left < right) {
if(numbers[left] == target-numbers[right])
break;
else if(numbers[left]+numbers[right] > target) {
right--;
}else {
left++;
}
}
return new int[]{left+1,right+1};
}
}
2、平方数之和
题解：
本题与上题类似，都是从有序数组里找到和为给定值的两个数，不同之处在于本题两个数为求平方后的数字。
考虑到左指针从0开始搜索，因此右指针不必从目标值开始搜索（也会导致数字越界），应该使用目标值开根号作为右指针起点。
原因是：如果右指针开根号后就等于目标值，那么ok，直接返回true；否则应该尝试增大左指针，意思是右指针最大边界就是目标值开根号。
其他步骤与上个问题相同。
注意点：本题是不可以进行left *left + right *right== c判断的。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tYc0zukt-1635940912887)(C:\Users\86159\AppData\Roaming\Typora\typora-user-images\image-20211029100826142.png)]
对于以上输入，直接不断增加left会导致越界问题，进而使判断失败。应该使用减法判断。
class Solution {
public boolean judgeSquareSum(int target) {
if (target < 0) return false;
int i = 0, j = (int) Math.sqrt(target);
while (i <= j) {
int powSum = i * i + j * j;
if (powSum == target) {
return true;
} else if (powSum > target) {
j--;
} else {
i++;
}
}
return false;
}
}
3、反转字符串中的元音字母
题解：
交换首尾元素的字母，最简单的方式就是使用双指针分别找到字符串前后两个位置的元音字母。
注意点：
- 可以使用哈希集合保存所有的元音字母，要知道常用的api。
- 交换完成的条件为left>=right。要注意判别left是始终小于right才进行交换。本题解的循环体写的比较好，确保了这一问题不会出现。
- 交换字母要小心，我下面的写法是错误的。
public void swap(char[] sArray,int left,int right) {
int tmp = left;
sArray[left] = sArray[right];
sArray[right] = sArray[tmp];
}
以上写法是把left暂存为tmp，然后right–>left,tmp–>right。问题出在tmp保存的只是下标，而下面两行交换的是具体的数组值。即我虽将left暂存了，但是我随后把left的数组值给修改了，自然无法完成交换。（不知道这样说的明不明白，QAQ）
正确的做法是一步到位:
class Solution {
public String reverseVowels(String s) {
HashSet vowels = new HashSet<>();
vowels.add('a');
vowels.add('e');
vowels.add('i');
vowels.add('o');
vowels.add('u');
vowels.add('A');
vowels.add('E');
vowels.add('I');
vowels.add('O');
vowels.add('U');
char[] sArray = s.toCharArray();
int left = 0,right = s.length()-1;
while(left < right) {
if(!vowels.contains(sArray[left])){
left++;
continue;
}
if(!vowels.contains(sArray[right])){
right--;
continue;
}
swap(sArray,left,right);
left++;
right--;
}
return new String(sArray);
}
public void swap(char[] sArray,int left,int right) {
char tmp = sArray[left];
sArray[left] = sArray[right];
sArray[right] = tmp;
}
}
4、验证回文字符串 Ⅱ
题解：
可以额外删除一个元素，并不是直接的能想到思路。举个具体的例子吧：比如字符串：abccdba。左指针移动到下标2，右指针移动到4时，左右指针的数组值不相等。此时有两种选择，**右移左指针（删除左指针元素），左移右指针（删除右指针元素）。**二者只要有一个后续组成回文子串就可以。
注意点：
删除指针后的后续判断是或的关系。
判断字串是否回文，注意按照标准写法来。
class Solution {
public boolean validPalindrome(String s) {
int left = 0,right = s.length()-1;
boolean flag = true;
while(left < right){
//以下if的逻辑是错误的，因为在左移和右移指针都可以继续判断时，二者都应该尝试，而不是在前者（左指针）成立后，直接跳出判断
if(s.charAt(left) != s.charAt(right)){
return isPalindrome(s,left+1,right)||isPalindrome(s,left,right-1);
}
left++;
right--;
}
return true;
}
public boolean isPalindrome(String s,int left,int right){
while(left<right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
5、合并两个有序数组
题解：
最容易想到的思路是：双指针从前往后遍历两个数组，但是这必然会使第一个数组的元素不断后移，时间复杂度为O(m(m+n))。此时应该转换思路（不是第一次做也想不到啊。。。），将两个指针倒序向前遍历，这样会优先覆盖nums1的空白区域，一次遍历即可完成归并操作（O(m+n)）。
注意点：
双指针判别逻辑，其实相当于共有三个指针：point1，point2和total。逻辑如下：
- point1>=0 && point2>=0
- nums1[point1]>nums2[point2]
- nums1[point1]<=nums2[point2]
- point1>=0 && point2<0
- point1<0&&point2>=0
一步步写出即可。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// if(m == 0) return nums2;
// if(n == 0) return nums1;
int pointer1 = m-1;
int pointer2 = n-1;
int total = m+n-1;
while(total >= 0) {
if(pointer1>=0 && pointer2>=0) {
if(nums1[pointer1] > nums2[pointer2]) {
nums1[total--] = nums1[pointer1--];
}else {
nums1[total--] = nums2[pointer2--];
}
}
else if(pointer1>=0 && pointer2<0) {
return ;
}
else{
nums1[total--] = nums2[pointer2--];
}
}
}
}
6、 环形链表
题解：
求解环形链表题，有两种思路：
- 可以使用哈希set保存走过的节点，然后不断用新走到节点判断是否在set集合。这种方法一定能在第一次走到环形节点交点（第一次出现重复节点的地方）的时候就可以判断是环形节点，缺点是需要多余的空间；
- 可以使用快慢指针，快指针一次走两步，慢指针一次走一步。如果是环形的，必然会相交。这种方法不会占用多余的空间。（这种方法第一次做很难想到，慢慢积累吧）
注意点：
小心快指针出现空指针的情况判断：
fast!=null && fast.next!=null
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode slow = head;
ListNode fast = head;
while(slow!=null && fast!=null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
}
}
7、通过删除字母匹配到字典里最长单词
题解：
有两个主要问题：
- 对于字典里的单词，判别是否是给定字符串的子序列；
- 对于多个符合条件的单词，找到字典序最小的单词；
第一个问题用双指针可以解决，第二个问题可以先对集合按字典序排序，然后直接遍历即可。
注意点：
排序要熟悉api调用，此处复习一下对于集合的排序方法使用：
api名称：
Collections.sort(list);//按升序排列集合
Collections.sort(list,new Comparator<集合元素类型>(){
//重写compare方法
public int compare(String s1,String s2){//以String类型为例
return s1.compareTo(s2);//升序 此处的compareTo方法实现了两个字符串字典序的比较
return s2.compareTo(s1);//降序
//如果按照某一位字符升序排序
char c1 = s1.charAt(index);
char c2 = s2.charAt(index);
return c1 -c2;
}
});
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
int len = s.length();
Collections.sort(dictionary,new Comparator<String>() {//其实没必要实现Comparator接口
public int compare(String s1,String s2) {
return s1.compareTo(s2);
}
});
String res = "";
for(String d : dictionary) {
if(isSubString(d,s)) {
res = res.length() >= d.length() ? res : d;
}
}
return res;
}
public boolean isSubString(String d,String s) {
int l1 = d.length();
int l2 = s.length();
int p1 = 0;
int p2 = 0;
while(p1<l1 && p2<l2) {
if(d.charAt(p1)==s.charAt(p2)) {
p1++;
}
p2++;
}
return p1==l1;
}
}
8、移除元素
思路一：
思路一是比较直接的思路：双指针分别找到待移除的元素（慢）与需要保留的元素（快），其中快指针的下标要大于等于慢指针。
找到后交换即可，但是实现过程有些复杂。
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
if(len == 0) return 0;
int slow = 0;
int fast = 0;
while(slow < len && fast < len) {
if(nums[slow] != val){
slow++;
continue;
}
if(nums[fast] == val || fast < slow) {
fast++;
continue;
}
nums[slow] = nums[fast];
nums[fast] = val;
slow++;
fast++;
}
return slow;
}
}
思路二：
依然是快慢指针，其中我们主要考虑快指针的移动状态，每次循环快指针必移动一次，且如果指向的是需要保留的元素，那么就将该值覆盖到慢指针位置，随后快慢指针同时右移一位。
合理性说明：设想在给定的数组里，我需要去除所有给定值的元素，换言之：**我需要留下所有不是给定值的元素。**基于这一现实，我们将慢指针指向的范围（从左向右）视为所有要留下的元素集合。当快指针发现一个元素需要保留，就会把这个值传给慢指针对应位置，此时慢指针就把需要保存的元素记录下来。如果还是不好想，就把慢指针的工作放到一个新数组里，我不断遍历需要保留的元素，并放入新数组里，是不是相当于我不断遍历需要保留的元素，并放入旧数组的前方位置。
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
if(len == 0) return 0;
int slow = 0;
int fast = 0;
for(; fast<len; fast++) {
if(nums[fast]!=val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}