一.方法介绍

一.方法介绍

1.双指针法，双指针可以在一个循环里以满足各自条件的方式移动

主要用于遍历数组，两个指针指向不同的元素，协同完成任务。

若两个指针指向同一数组，遍历方向相同且不会相交，则称为“滑动窗口”（两个指针包围的地方即为当前的窗口），经常用于区间搜索，任意时刻，只有一个指针移动。
若两个指针指向同一个数组，而遍历方向相反，则可以用来进行搜索，待搜索的数组则经常是排好序的。

2.可以用双指针来判断圈：-佛洛依德判圈法

给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。

3.有序数组下的查找两数特定和

采用首尾指针法，start指向头处，end指向尾处-（167题）

4.一遍双指针解决荷兰国旗问题

问题描述

给定一个数组和一个target目标，给这个数组排序，要求分成三段，第一段都小于target，第二段都等于target，第三段都大于target。

时间复杂度O(N)，不能有额外的空间复杂度。

解决算法

参见75.颜色分类 ```cpp void Flag_of_Netherland(vector& nums,int target) { int lens=nums.size(),i,p=0,q=nums.size()-1,tmp; for (i=0;i<nums.size();i++){

 if (nums[i]<target) {
     tmp=nums[i];
     nums[i]=nums[p];
     nums[p]=tmp;
     p++;
 }
 if (nums[i]>target){
     tmp=nums[i];
     nums[i]=nums[q];
     nums[q]=tmp;
     q--;
    if (nums[i]<target)
            --i;
 }

} return; }

//另一种写法，有问题？ void flag_of_netherland(int *arr, int n, int target){ int i=0,j=0, k=n-1; int temp; while(j<=k){

    if(arr[j]<target){
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
        i++,j++;
       //这里之所以要j++，是因为不可能出现arr[i]>target的情况，否则早就在前面的遍历时交换掉了
    }else if(arr[j]>target){
        temp=arr[k];
        arr[k]=arr[j];
        arr[j]=temp;
        k--;// 这会不能j++,因为你不知道换过来的是个啥东西
    }else{
        j++;
    }
}

}

<a name="3ConE"></a>
## 5.前缀和与差分

1. 两者是相互对应的关系，对差分可以求前缀和得到原数组。
1. 差分数组对应的概念是前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 i 个数即为原数组的第 i-1 个元素和第 i 个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组。
1. 差分数组的性质是，当我们希望对原数组的某一个区间 [l,r] 施加一个增量 inc 时，差分数组 d 对应的改变是：d[l] 增加 inc，d[r+1] 减少 inc。这样对于区间的修改就变为了对于两个位置的修改。并且这种修改是可以叠加的，即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。




<a name="5misx"></a>
# 二.leetcode相关习题

<a name="xib8z"></a>
## 42.接雨水-理解一点maxmin
[题目链接](https://leetcode-cn.com/problems/trapping-rain-water/)

1. 很关键的一点：下标 i 下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值maxmin，其实也很好理解，短板效应。于是下标 i 处的雨水量等于maxmin-height[i]，于是问题转化为求出每个下标 i 处的对应的maxmin，然后遍历求和。 
1. 常规解法需要O(n^2) 的两次对于height数组的遍历。
1. 动态规划法，left[i]表示下标 i 及其左边位置的最大值，right[i]表示下标 i 及其右边位置的最大值，left[0]=height[0]，right[n-1]=height[n-1]。left[i]=max(height[i], left[i-1])，right[i]=max(height[i], right[i+1])，这个可以通过一次遍历得到，然后对于每个下标 i ，求出maxmin=min(left[i], height[i])。
1. 双指针法：理解了上面的算法，可以只用四个变量来代替上面的left和right数组。下面是算法，leftmax保留的是下标left及其左边的最大值，rightmax则保留的是下标right及其右边的最大值，于是，每次先更新leftmax和rightmax，并且若height[left]>=height[right]，则表明leftmax>=rightmax的，根据1，此时在区间[left,right]的值无论是什么，都不会对下标right的maxmin有影响了，此时maxmin=rightmax。然后顺势求出right对应的雨水量即可。然后right--，同理如此。
```cpp
 int trap(vector<int>& height) {
        int leftmax=height[0],rightmax=height[height.size()-1],sum=0,left=0,right=height.size()-1;
        while (left<right) {
            leftmax=(leftmax>height[left])?leftmax:height[left];
            rightmax=(rightmax>height[right])? rightmax:height[right];
            if (height[left]>=height[right]) {
                sum+=(rightmax-height[right]);
                right--;
            }else {
                sum+=(leftmax-height[left]);
                left++;
            }
        }
        return sum;
    }

11.盛最多水的容器

题目链接
(短板移动法,从公式和常识的角度理解)
解法1: 双指针法-移动最差的
1.设置双指针i,j分别位于容器壁的两端，由下述规则来移动指针
2. 设每一状态下水槽面积为S(i,j)，而水槽的实际高度由两板中的短板决定，可得公式S(i,j)=min(h[i],h[j])x(j-i)
3.在每一个状态下，对于短板或长板收窄一格，则导致水槽底边宽度-1;
4.因此，向内移动短板，水槽的短板min(h[i],h[j])可能变大，水槽面积S(i,j)也可能变大，而向内移动长板，水槽面积则可能不变或者变小
因此，能够找到最大水槽面积的，只能是向内移动短板，这种方式节省下来的遍历状态都不会丢失面积最大值。

26.删除有序数组中的重复项

题目链接
第26题(删除有序数组中的重复项)也是双指针的应用，是将后面的不同的项复制到前面来就行

27.移除元素

题目链接
双指针复制移动，从后往前移动；
双指针交换复制移动，由于不需要讲究删除后的数组的顺序，从前往后遍历时，
每次发现和要删除元素相同的元素时，将数组最后一个元素复制过来，然后数组长度减一，然后再检查这个元素，若和要删除元素不同，
则继续往后移动

88.合并两个有序数组

题目链接
这题的设巧之处在于，两个数组都是排好序的，其中一个数组后面有以0做填充的空位。
把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。
因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，再额外创立一个 pos 指针，起始位置为 m +n−1。每次向前移动 m 或 n 的时候，也要向前移动 pos。这里需要注意，如果 nums1 的数字已经复制完，还需要nums2的数字继续复制；如果 nums2 的数字已经复制完，剩余 nums1 的数字不需要改变，因为它们已经被排好序。

142.环形链表||

题目链接
要点1：Floyd循环查找判圈法—快慢指针思想，龟兔赛跑
给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。
要点2：已知有圈，如何找到圈的入口
设链表共有 a+b 个节点，其中链表头部到链表入口有 a 个节点（不计链表入口节点），链表环有 b 个节点，并且a和b显然是未知的；设两指针分别走了 f，s 步，则有如下的关系：（a、b、n都是未知的，并且也不需要提前知道值）
fast 走的步数是slow步数的 2 倍，即 f = 2s；
fast 比 slow多走了 n个环的长度，即 f = s + nb；（解析：双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走环的长度整数倍）；
以上两式相减得：f = 2nb，s = nb，即fast和slow 指针分别走了 2n，n 个环的周长。
若让指针从链表头部一直向前走并统计步数k，那么所有走到圈入口节点时的步数是：k=a+mb（m是非负整数）（先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）。
通过上述论述可以发现，在得到有圈时两个指针会在圈内重合，这时，将fast再次指向链表头结点，一步一走走a步，slow则同时也一步一走走a步，可以得到在圈入口处,fast和slow会相遇，fast的k=a，而slow的k=a+nb。

287.寻找重复数

题目链接

由于范围是在1~N中，而数组下标范围是1~N+1，所以一定不会超过下标。
下标->值，相当于一次链表链接，相同的值一定会造成这链表出现环。

然后可以用链表的判圈法

int findDuplicate(vector<int>& nums) {
     int i, slow=0 ,fast=0;
     while (slow==0||slow!=fast) {
         slow=nums[slow];
         fast=nums[fast];
         fast=nums[fast];
     }
     slow=0;
     while (fast!=slow){
         slow=nums[slow];
         fast=nums[fast];
     }
     return slow;
 }

167.两数之和

题目链接
有序数组下的查找两数特定和
解法一:双指针法
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
每次计算两个指针指向的两个元素之和，并和目标值比较。
如果两个元素之和等于目标值，则发现了唯一解。
如果两个元素之和小于目标值，则将左侧指针右移一位。
如果两个元素之和大于目标值，则将右侧指针左移一位。
移动指针之后，重复上述操作，直到找到答案。
解法二: 遍历加上二分查找
从左到右确定一个数的下标n，然后每次在该数的右边，进行二分查找target-nums[n]

202.快乐数-(判循环圈)

题目链接

无论起始的数有多大，最终的结果都只可能有如下三种 1.最终会得到1; 2.最终会进入循环;3.值会越来越大，最后接近无穷大而假设最大位数是三位数，最大为999，得到243，会越来越小，位数也会由大逐渐变小，因此第3种情况不存在。
解法一：
把每次变换的一次作为一次移动，slow移动一次，fast移动两次。
如果是快乐数，则fast最终的移动结果一定是1，并且在1一直停留, slow也会往1移动。如果不是快乐数，则会存在一个循环，slow和fast会在不是等于1的地方相遇相等。

解法二：
实际只有一个循环：4->16->37->58->89->145->42->20->44->16->37->58->89->145->42->20->4。所有其他数字都在进入这个循环的链上，或者在进入1的链上。

283.移动零

题目链接
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：
左指针左边均为非零数；
右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

633.平方数之和

题目链接
和167题一样，不过有一点要注意的是，由于是平方和，所以sum要用long存储，否则可能会超过int型。

15.三数之和

题目链接

先对nums数组进行排序，方便在遍历的时候找规律
设置个next和before数组，对排序后的nums进行规律探查（比如-1,-1,1,1,2），其next数组就是（2,1,2,1,1,）其before数组就是（1,2,1,2,1），是为了标注重复的位置

先确定第一个数，然后剩下的两个数利用首尾双指针法（和167题类似）在数组中去找

vector<vector<int>> threeSum(vector<int>& nums) {
     vector<vector<int>> res;
     vector<int> next(nums.size()),before(nums.size());
     if (nums.size()<3)
         return res;
     sort(nums.begin(),nums.end());
     int i,j,lens=nums.size(),k;
     for (i=0;i<lens;) {
         for (j=1;(i+j)<lens&&nums[i]==nums[i+j];j++);
         next[i]=j;
         i=i+1;
     }
     for (i=lens-1;i>=0;) {
         for (j=1;(i-j)>=0&&nums[i]==nums[i-j];j++);
         before[i]=j;
         i=i-j;
     }
     for (i=0;i<lens;i=i+next[i]) {
         for (j=i+1,k=lens-1;j<k;) {
             int sum=nums[i]+nums[j]+nums[k];
             if (sum==0){
                 res.push_back(vector<int>{nums[i],nums[j],nums[k]});
                 j=j+next[j];
                 k=k-before[k];
             }else if (sum>0){
                 k=k-before[k];
             }else {
                 j=j+next[j];
             }

         }
     }
     return res;   
 }

61.旋转链表-环形链表链接

题目链接

设链表的长度为len，则链表的节点每向右移动的个数k是len的整数倍，就会回到原来的位置，相当于没有移动。
将链表的首尾连接起来，组成环形链表，然后切开。

新链表的尾部在len-(k%len)，相当于把原来链表头结点head向右移动len-1-(k%len)个位置。

ListNode* rotateRight(ListNode* head, int k) {
     if(k==0||head==nullptr||head->next==nullptr)
         return head;
     int lens=1;
     ListNode* ptr=head;
     while (ptr->next!=nullptr) {
         ptr=ptr->next;
         lens++;
     }
     int add=lens-k%lens;
     if (add==lens)
         return head;
     ptr->next=head;
     ptr=head;
     while(add>1){
         ptr=ptr->next;
         add--;
     }
     head=ptr->next;
     ptr->next=nullptr;
     return head;    

 }

剑指Offer57-||. 和为s的连续正数序列

题目链接
双指针start和end

start从1开始，end从2开始，sum是区间[start,end]的和
当sum小于target时，end需要往后移动；当sum等于target时，表示找到一组，将[start,end]作为数组存入结果中；当sum大于target时，start往前移动一个。

由于最少需要两个数，因此，start<target/2+1。

 vector<vector<int>> findContinuousSequence(int target) {
     vector<vector<int>> res;
     int start,end,sum,i;
     for (start=1,end=2,sum=start+end;start<(target/2+1);) {
         if (sum<target){
             end++;
             sum+=end;
         }else if (sum==target){
             vector<int> row;
             for (i=start;i<=end;i++)
                 row.push_back(i);
                 res.push_back(row);
                 sum-=start;
                 start++;
         }else{
             sum-=start;
             start++;
         }
     }
     return res;
 }

75.颜色分类

题目链接
经典的荷兰国旗问题

方法一：计数法

通过一次遍历统计数组中0,1,2的个数，然后再根据这些去重写数组。

方法二：两遍双指针
第一次遍历，指针 i 遍历数组，指针 p 停在全是数字0的位置的下一个（初始位置为下标0）。一次遍历把数组中的0交换到最前面。
第二次遍历，指针i从上一次遍历的p开始，继续把数组中的1交换到0的后面。

方法三：一遍双指针
p指向挑选好全0的位置的下一个位置，q指向全2的位置的上一个位置，初始时p=0, q=nums.size()-1
i 从头开始遍历，遇到0则和p交换，遇到2则和q交换

注意一点，一定要保证被交换到中间的是1.

void sortColors(vector<int>& nums) {
     int p = 0, q = nums.size() - 1;
     for (int i = 0; i <= q; ++i) {
         if (nums[i] == 0) {
             nums[i] = nums[p];
             nums[p] = 0;
             ++p;
         }
         /*这个先0后2的先后顺序就保证了上面的交换，即使是nums[p]=2被交换到nums[i]处
         也能及时处理掉，而不是被跳过，也因为如此，才有下面的--i的回退。*/
         if (nums[i] == 2) {
             nums[i] = nums[q];
             nums[q] = 2;
             --q;
             //下面这个是假设和nums[i]交换的nums[q]是0的话，还得把i保持在原地，和前面的交换。
             if (nums[i] != 1) {
                 --i;
             }
         }
     }
     return;
 }

1109.航班预定统计-（差分）

题目链接

题目明显条件：只给了某一段区间的增量，并且双循环会超时。

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
     vector<int> nums(n);
     for (auto& booking : bookings) {
         nums[booking[0] - 1] += booking[2];
         if (booking[1] < n) {
             nums[booking[1]] -= booking[2];
         }
     }
     for (int i = 1; i < n; i++) {
         nums[i] += nums[i - 1];
     }
     return nums;
 }

238.除自身以外数组的乘积

题目链接

定义数组L[]、R[]，其中L[i]表示下标i左边（不包括i）所有数的乘积，R[i]表示下标 i 右边（不包括 i ）所有数的乘积，这两个数组各通过一次遍历即可得到，然后ans[i]=L[i]*R[i]。

要在常数空间复杂度完成，则可以利用存储答案的ans[]来先存储L[]，然后再用一个变量来实时代替R[]。

 vector<int> productExceptSelf(vector<int>& nums) {
     int lens=nums.size(),i,j,sum=1;
     vector<int> ans(lens);
     for (i=0;i<lens;i++) {
         ans[i]=(i==0)?1:ans[i-1]*nums[i-1];
     }
     for (i=lens-1;i>=0;i--){
         ans[i]=ans[i]*sum;
         sum*=nums[i];
     }
     return ans;
 }

双指针法

一.方法介绍

1.双指针法，双指针可以在一个循环里以满足各自条件的方式移动

2.可以用双指针来判断圈：-佛洛依德判圈法

3.有序数组下的查找两数特定和

4.一遍双指针解决荷兰国旗问题

问题描述

解决算法

11.盛最多水的容器

26.删除有序数组中的重复项

27.移除元素

88.合并两个有序数组

142.环形链表||

287.寻找重复数

167.两数之和

202.快乐数-(判循环圈)

283.移动零

633.平方数之和

15.三数之和

61.旋转链表-环形链表链接

剑指Offer57-||. 和为s的连续正数序列

75.颜色分类

方法一：计数法

方法二：两遍双指针

方法三：一遍双指针

1109.航班预定统计-（差分）

238.除自身以外数组的乘积