(卡哥双指针篇打卡)
1.移除元素思路
- 可以直接暴力求解。但是时间复杂度会很大。有个更简单的办法就是快慢指针。这种快慢指针的思路就是，slow指针指向插入字符位置（把数组当成新的一个数组），fast指针指向需要验证的字符上。
- 相当于就是fast往后面验证字符是否等于val
- 如果是那么fast往后走，slow不需要进行插入val和往后走。
- 如果不是那么fast还是往后面走，但是slow需要插入val并且往后面走
class Solution {
public int removeElement(int[] nums, int val) {
int slow=0;
for(int fast=0;fast
2.反转字符串
思路
左右指针。left和right指针，放在数组头和数组尾。并且通过while(leftright那么就结束循环，交换s[left]和s[right]。时间复杂度是n
class Solution {
public void reverseString(char[] s) {
int left=0;
int right=s.length-1;
while(left
3.替换空格
思路
遍历整个字符串，创建一个StringBuilder,如果发现遍历的字符是空格那么就加入%20进StringBuilder,如果不是那么就加入原来的字符进StringBuilder。时间复杂度是n，空间复杂度也是n（因为基本上把原来的字符赋值给新的字符串）.
拓展
之所以要创建一个StringBuilder原因就是String是不可变，需要通过一个新的字符串来接收修改之后的字符串。
class Solution {
public String replaceSpace(String s) {
StringBuilder sb=new StringBuilder();
for(int i=0;i
4.反转字符串里的单词
思路
①先去掉空格。利用首尾指针，如果发现是空格，那么start++和end–。接着就是继续遍历这个范围的字符串，并且加入到StringBuilder中，如果发现StringBuilder最后一个字符不是空格那么才能加入空格。其它字符正常加入。
②接着就是反转字符串之后，再反转一次所有字符串的单词。
③反转字符串直接用首尾指针来进行反转（记住传入的长度是StringBuilder而不是原来的那个串的长度）
④最后就是反转单词，利用快慢指针。end指针去探测空格，如果找到那么start到end就是一个单词，可以交给之前写好的反转字符串方法来反转，并且切换到下一次的遍历。也就是start去到end+1也就是空格后面的单词，end继续往后面遍历。
class Solution {
public String reverseWords(String s) {
StringBuilder sb=removeSpace(s);
reverseString(sb, 0, sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
//1.去掉多余的空格
private StringBuilder removeSpace(String s){
int start=0;
int end=s.length()-1;
//1.去掉首尾空格
while(s.charAt(start)==' ') start++;
while(s.charAt(end)==' ') end--;
//2.去掉中间的空格，sb最后一个不是空格才能加入空格,因为单词间只有一个空格
StringBuilder sb=new StringBuilder();
while(start<=end){
char c=s.charAt(start);
if(c!=' '||sb.charAt(sb.length()-1)!=' '){
sb.append(c);
}
start++;
}
return sb;
}
//2.反转字符串(首尾指针)
private void reverseString(StringBuilder sb,int start,int end){
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
//3.反转字符串中的单词
private void reverseEachWord(StringBuilder sb){
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
5.反转链表
双指针法
思路
就是一个cur指向当前节点，pre指向前一个节点，然后通过temp先保存原本cur的next，然后再修改cur的next指向pre。相当于就是temp先到cur的后面一个节点，然后cur完成next指针的指向。本质就是修改每一个节点的next指向。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur=head;
ListNode temp;
ListNode pre=null;
while(cur!=null){
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
}
递归法
思路
本质上和双指针法一模一样。 不同的只是没有进行赋值交换。而是当前递归的cur当做是pre，temp当做是新的cur。然后交给下一次的递归处理指针指向
class Solution {
public ListNode reverse(ListNode pre,ListNode cur){
if(cur==null) return pre;
ListNode temp=cur.next;
cur.next=pre;
return reverse(cur,temp);
}
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
}
总结：无论是递归法还是双指针法，他们本质目标就是为了改变指针的指向。①提前保存下一个节点②改变指向③给新的pre和cur赋值进入到下一轮的指向修改。
6.删除倒数第n个节点
思路
快慢指针。本质就是fast先走n步，那么fast和slow的距离就是n。那么这个时候只需要fast走到等于null的时候，那么slow的位置就是fast-2的位置，fast在链表最后，也就是说slow就在链表的倒数第二个上面。但是为了slow可以删除倒数第n个，所以fast走n+1步。让slow走到待删除节点的前一个节点.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode fast=dummy;
ListNode slow=dummy;
//先让fast移动n+1个，也就是slow与fast之间的距离是n+1，方便slow删除下一个节点
int l=n+1;
while(l-->0){
fast=fast.next;
}
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
slow.next=slow.next.next;
return dummy.next;
}
}
7.链表相交
思路
①可以使用浪漫相遇。意思就是如果A与B有相交节点那么他们就有一段公共的路程c。A到交点的距离是a，B到交点的距离是b。那么B走完全乘就是b+c,A走完全程就是a+c.如果他们再走一段对方到交点的距离就是b+c+a和a+c+b，也就是他们会在走对方的路过程中同时走到交点或者是走到null没有相交。也就是他们一定会相遇。
②还有一种解法就是两个链表出现相交的地方一定是最短链表的后半部分和长链表的后半部分（因为指针相同，那么next也必定是相同的），所以可以先让长链表的指针移动到短链表的长度+1的位置。然后再开始两个链表的遍历，并对比，如果找到相同的那么就是交点。这种求解很麻烦，需要求两边长度，然后求gap，移动长链表，最后才是对比。相比第一种很不简洁。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode h1=headA;
ListNode h2=headB;
while(h1!=h2){
//如果没有走完自己的继续走，如果走完就去走别人的路。
h1=h1==null?headB:h1.next;
h2=h2==null?headA:h2.next;
}
return h1;
}
}
8.环形链表2
思路
先用快慢指针判断是不是环形链表。如果不是那么fast指针就会走到null，并且终止循环。如果是循环链表那么就会走到fast==slow的时候。这个时候就需要找这个环形入口。环形入口其实是根据。fast与slow指针相遇的那个点到环形入口，和链表头结点到入口的距离相等。这个计算其实就是链表头到环形入口是x距离，环形入口到相遇是y。相遇点再到环形入口是z。(x+y)*2快指针走过的距离等于慢指针走过的距离乘2，快指针自己走过的距离是x+y+ n * (y+z),这个时候的出来x=nz+(n-1)y。当n=1的时候x=z，当n>1的时候你会发现只是多走了一个z+y也就是一圈，对x=z并没有影响。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(fast==slow){
fast=head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return fast;
}
}
return null;
}
}
9.三数之和
思路(排序+双指针)
可以通过双指针来进行计算。先把数组进行排序，然后就是for遍历一次，如果发现nums[i]也就是初始的那个值都要>0了那么后面的肯定都是大于0那么可以直接返回结果。如果是nums[i]==nums[i-1]的话就需要去重，因为后面出现的组合会与之前的相重合。最后就是通过双指针left和right一头一尾来进行去重遍历，如果计算出来的nums[i]+nums[left]+nums[right]也就是sum，大于0就要让right左移，原因是这个数组排序了，要把sum减小就要right左移。相反就是left右移。如果发现left和right的下一个是相同的那么就循环跳过（去重）。
时间复杂度是nlogn(排序)+n（遍历数组）*n（双指针）
class Solution {
public List> threeSum(int[] nums) {
List> res=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i0那么就直接返回结果
if(nums[i]>0) return res;
//如果与上一个相同，那么就跳过去重
if(i>0&&nums[i]==nums[i-1]) continue;
int left=i+1;
int right=nums.length-1;
//接着就是通过左右指针，去重，和找值计算。如果符合那么就放入res，并且查看下一个left或者right是不是重复的。如果计算出来的值，比较大，那么right左移，如果是比较小那么就是left右移
while(left0){
right--;
}else if(sum<0){
left++;
}else{
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(right>left&&nums[right]==nums[right-1]) right--;
while(right>left&&nums[left]==nums[left+1]) left++;
right--;
left++;
}
}
}
return res;
}
}
10.四数之和
思路
四数之和与三数之和的思路基本一致。只不过就是多了一层循环罢了。这里使用双指针方便去重，而且能够降低暴力循环的复杂度。本质就是确定好两个数（去重），然后就是通过双指针来遍历（代替for，不然也可以直接暴力。）去重。去重的关键就是排序。
class Solution {
public List> fourSum(int[] nums, int target) {
List> res=new ArrayList<>();
Arrays.sort(nums);
for(int k=0;k0&&nums[k]==nums[k-1]) continue;
for(int j=k+1;jk+1&&nums[j]==nums[j-1]) continue;
int left=j+1;
int right=nums.length-1;
while(lefttarget){
right--;
}else if(sumleft&&nums[right]==nums[right-1]) right--;
while(right>left&&nums[left]==nums[left+1]) left++;
right--;
left++;
}
}
}
}
return res;
}
}
总结：快慢指针、首尾指针用到比较多。快慢指针可以解决环，倒数，去掉某些值的问题，首位指针可以解决反转、去重、等问题。
