一、相向双指针

利用数组已经排序的性质，两数相加和target比较大小，可以知道整个数组和target的关系。

【一定要找到一个我们能明确知道大了是往哪移，小了是往哪移动的情况才能套用这个方法。即固定的那个数不能是随便固定的。】

1、两个数

从两端开始，left=2, right=8。此时left + right=10 > target。由于排序的性质，所以8加上2右边的任何一个数都是大于target的，不符合要求，可以直接去掉8，即右指针左移。

2、三个数

延伸到三个数，就是先固定一个数，然后另外两个数套用这个相向双指针。

练习

例题：两数之和、三数之和

练习：

2824统计和小于目标的下标对数目

16最接近的三数之和

18四数之和：外面分别固定两个数，然后里面两个数使用相向双指针。

611有效三角形的个数：与其他题目的区别是，只有固定最长边，我们才能知道两外两边之和小了是左指针往右移，大了是右指针往左移（此时固定右指针，左指针往右移的所有情况，一定是符合条件的，所以直接计算个数，然后去掉右指针指向的这个数）。

二、相向双指针2

例题：盛最多水的容器、接雨水

1、盛最多水的容器

依然是相向双指针，在左右指针中，如果左指针指向的墙壁低于右指针（容器能存储的量取决于左指针），那么固定左指针，右指针在左移的过程中，宽度减小，高度不变（右指针的高度大于等于左指针的）或减小（右指针的高度出现小于左指针的情况），所以容量肯定减小，那就不需要考虑了。所以直接右指针左移。

左指针高度高于右指针的情况同上分析。

2、接雨水

本质是看它左侧最大墙壁高度和右侧最大墙壁高度。

如果所有左侧墙壁的最大高度或者右侧墙壁最大高度低于当前墙壁i的情况时，这一竖列就不可能接到水。因为它会从左侧或者右侧流出。

只有当左侧墙壁的最大高度和右边墙壁的最大高度都高于当前墙壁，它才能接到水。竖列i接到水的量 = 左右侧最低的那面墙 - 当前i墙壁的高度。

方法一、前后缀分解

分别使用循环计算每个竖列的左侧/右侧墙壁的最大高度。

再用一个循环统计每个竖列接到的水量。

方法二、相向双指针

用O(1)的时间复杂度去知道O(n)时间复杂度的内容。

左右指针从两头开始移动，当左指针低于右指针时，就可以确定左指针当前的竖列的存水量了，因为是根据左右两侧矮的那一边计算，虽然还不知道右边实际的高度，但是已经存在比左边高的情况了，后面无论高低都不影响这个竖列存左指针-当前高度的水了。

同理，如果右指针低于左指针，那就可以确定右指针当前竖列的存水量了。

三、滑动窗口（毛毛虫挪动法）

用于解决子数组问题，某条件下最短/最长/方案数

1.维护一个有条件的滑动窗口；

2.右端点右移，导致窗口扩大，是不满足条件的罪魁祸首；

3.左端点右移目的是为了缩小窗口，重新满足条件

例题：209长度最小的子数组、713 乘积小于 K 的子数组、3无重复字符的最长子串

伪代码模板

// 索引区间 [left, right) 是窗口
int left = 0, right = 0;

while (right < nums.size()) {
    // 增大窗口
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.removeFirst(nums[left]);
        left++;
    }
}

何时使用？

1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？

2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？

3、什么时候应该更新结果？

如果能回答这三个问题，就可以使用滑动窗口。

1、无重复字符的最长子串

右指针往右移来吸纳字符，如果吸纳的这个字符已经存在，那么左指针右移，直到右指针的这个字符只剩下一个。此时就是无重复字符子串。反复固定右指针，然后缩左指针，进行循环就可以获得无重复字符的最长子串。

四、二分查找（红蓝染色法）一-五未复习

练习：1385. 两个数组间的距离值

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int x : arr1) {
            int i = Arrays.binarySearch(arr2, x - d);
            if (i < 0) {
                i = ~i; // -i - 1
            }
            if (i == arr2.length || arr2[i] > x + d) { 
                ans++;
            }
        }
        return ans;
    }
}

i == arr2.length 表示要插入的地方是数组末尾，说明所有元素都 < x-d

arr2[i] > x + d 表示第一个**>=x-d**的数已经>x+d了，所以 [x-d, x+d] 无元素。（其中的 i 就是前面用二分查找找到的第一个 >=x-d 的数的下标。）

Arrays.binarySearch()

找到元素：返回索引（非负数）（0 ~ length）
没找到元素：返回”应该插入的位置” -(insertionPoint) - 1

示例：

int[] arr = [1, 3, 5];
Arrays.binarySearch(arr, 0);  // 返回 -1
// 0 应该插在索引 0 处：-(0) - 1 = -1

Arrays.binarySearch(arr, 4);  // 返回 -3
// 4 应该插在索引 2 处：-(2) - 1 = -3

查找峰顶

旋转排序数组

寻找最小值

和最右边的end比，如果中点小于end，那么中点已经为最小值或者在最小值右侧。如果中点大于end，那只能是右边的那种情况，并且它在最小值左侧。

寻找target

什么时候染色是染蓝色？也就是什么时候mid是target或者在target的右侧？

mid在左边，即mid > end
1. 此时左边的情况不可能，只有可能是右边的情况，并且右边只有一种情况，那就是mid >= target
mid在右边，即mid < end
1. target在左边，即target > end
2. target也在右边，但是mid > target

五、快慢指针 + 反转链表

快慢指针

fast指针一次走两步，slow一次走一步。

当fast的next为空（奇数个节点），或者fast为空时（偶数个节点），slow正好就是中间节点。

是否有环

如果有环，在环中，fast相对于slow的速度是1，在某一时刻，肯定会和slow相遇。

环的入口

slow和fast相遇时，slow肯定没有走完一圈。（假设slow刚到入口时，fast在它前面一个，这是距离最大的情况。此时fast也只需要走n-1次【n为环中节点个数】）

slow走了a+b，fast走了a+b+k(b+c)，而2(a+b) = a + b + k(b+c)

得到a-c = (k-1)(b+c) 也就是说a= (k-1)(b+c) + c，那么在相遇的时候头结点开始走，走了a步以后一定会和slow在入口相遇。

六、删除链表节点

要删除第n个节点，就是把第n-1个节点的next指向第n个的next。

1、从链表中移除在数组中存在的节点

按常规来说，需要用循环遍历数组中的元素，同时还要遍历整个链表，是$$O(n^2)$$的。

先通过循环把数组中的元素存入 HashSet，这样后面比较元素的时候使用set.contains()，查询就变成$$O(1)$$的了。

整体是$$O(n)$$的（仍需要遍历链表）。

2、从链表中移除右侧有更大数值的节点

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

从左往右，需要考虑一个节点的所有右边的节点（右边全是没处理过的节点），需要双重循环。

但是，如果把链表翻转，就变成了保证一个节点左边没有比它大的。而左边是已经处理过的节点，只需要每次判断一个节点是否比右边的节点大，如果大就删除右边的这个节点，然后继续判断。当出现右边节点比左边节点大后，就可以把cur转到右边这个节点了。右边这个节点就一定满足要求了，因为左边保留了最大的那个节点和它比较。