一、相向双指针

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

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

1、两个数

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

image-20251214212004096

2、三个数

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

练习

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

练习：

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

16最接近的三数之和

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

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

二、相向双指针2

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

1、盛最多水的容器

image-20251215120425183

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

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

2、接雨水

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

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

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

image-20251215121405835

方法一、前后缀分解

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

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

方法二、相向双指针

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

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

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

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

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

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

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

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

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

伪代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 索引区间 [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. 两个数组间的距离值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

示例：

1
2
3
4
5
6
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

查找峰顶

image-20251225211022104

旋转排序数组

寻找最小值

image-20251225211221578

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

寻找target

image-20251225211741053

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

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