双指针算法

双指针算法模板：

for(int i = 0, j = 0; i < n; i++) {
    while(j < i && check(i, j)) {
        j++;
    }
       // 题目具体逻辑
}

基本上双指针算法的模板就是这样，check()函数指j满足某种条件。

核心思想

双指针的算法的核心思想在于把复杂度为O(n ^ 2)的朴素算法优化到O(n)：

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {

    }
}
将上面的朴素算法优化到O(n)

题目列表

题目名称	难度
16. 最接近的三数之和	Medium
167. 两数之和 II - 输入有序数组	Easy
658. 找到 K 个最接近的元素	Medium
42. 接雨水	Hard
Acwing 800. 数组元素的目标和	Easy
AcWing 799.最长连续不重复子序列	Easy
AcWing 2816. 判断子序列	Easy

这几个题目都是非常经典的双指针算法题目，需要好好掌握~~

800. 数组元素的目标和

题目链接：https://www.acwing.com/problem/content/802/

---

思路：采用双指针算法，定义两个指针i和j，其中i在A数组开始位置，j在B数组结束位置。

A[i] + B[j] > x：j--

可套上述模板解决：

#include 
#include 

using namespace std;

const int N = 100010;
int n;
int m;
int x;
int A[N], B[N];

int main() {
    // 处理输入输出
    cin >> n >> m >> x;
    for(int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for(int i = 0; i < m; i++) {
        cin >> B[i];
    }
    // 双指针算法
    for(int i = 0, j = m - 1; i < n; i++) {
        while(j >= 0 && A[i] + B[j] > x) {
            j--;
        }
        if(A[i] + B[j] == x) {
            cout << i << " " << j << endl;
            break;
        }
    }
    return 0;
}

799. 最长连续不重复子序列

题目链接：https://www.acwing.com/problem/content/801/

---

思路：不断枚举i，i前j后，当发现某个数出现次数大于一时，j往前移动一位。

代码直接套模板即可：

#include 
#include 

using namespace std;

const int N = 100010;
int n;
int arr[N], s[N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int res = 0;
    for(int i = 0, j = 0; i < n; i++) {
        s[arr[i]]++;
        while(s[arr[i]] > 1) {
            // j所在的位置次数减一
            s[arr[j]]--;
            // j往右移动一位
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

2816. 判断子序列

题目链接：https://www.acwing.com/problem/content/2818/

---

思路：两个数组，采用双指针，定义两个指针i和j，i指向a数组，j指向b数组，由于b.length >= a.length，所以我们经过每次循环，不论结果如何j++，而i只有匹配时再i++。

代码：

#include 
#include 

using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < m; i++) {
        cin >> b[i];
    }
    int i = 0, j = 0;
    while(i < n && j < m) {
        if(a[i] == b[j]) {
            i++;
        }
        j++;
    }
    if(i == n) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

注意：

为什么这题没有用模板？

当我们遇到像 AcWing 799.最长连续不重复子序列，AcWing 800.数组元素的目标和 这种问题，我们需要先固定一个指针，然后另一个指针去连续的判断一段区间，需要while()循环。换句话说，while()循环用来解决连续一段区间的判断问题；而这道题中我们需要对a数组和b数组的每一位，逐位去进行比较判断，i指针不断后移，而j指针只有当匹配成功时才后移一位，它不是连续一段区间的判断。

16. 最接近的三数之和

题目链接：https://leetcode-cn.com/problems/3sum-closest

---

思路：

• 首先进行数组排序

• 在数组 nums 中，进行遍历，每遍历一个值利用其下标 i，形成一个固定值 nums[i]

• 再使用前指针指向 start = i + 1 处，后指针指向 end = nums.length - 1 处，也就是结尾处

• 根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans

• 同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end–，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果。

代码：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.length; ++i){
            int start = i + 1, end = nums.length - 1;
            while(start < end){
                int sum = nums[i] + nums[start] + nums[end];
                if(Math.abs(target - sum) < Math.abs(target - ans)){
                    ans = sum;
                }
                if(sum > target){
                    end--;
                }else if(sum < target){
                    start++;
                }else{
                    return sum;
                }
            }
        }
        return ans;
    }
}

167. 两数之和 II - 输入有序数组

题目链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

---

题解参考这篇即可。

代码：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                return new int[] {left + 1, right + 1};
            }else if(sum < target){
                left++;
            }else if(sum > target){
                right--;
            }
        }
        return new int[] {-1, -1};
    }
}

658. 找到 K 个最接近的元素

题目链接：https://leetcode-cn.com/problems/find-k-closest-elements/

---

思路：

可以使用双指针算法将不符合条件的元素直接移除，这样最后返回的就是符合条件的元素了。

代码：

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - 1;
        int removeSize = arr.length - k;
        while(removeSize > 0){
            if((x - arr[left]) <= (arr[right] - x)){
                right--;
            }else{
                left++;
            }
            removeSize--;
        }    
        List<Integer> res = new ArrayList<Integer>();
        for(int i = left; i <= right; ++i){
            res.add(arr[i]);
        }
        return res;
    }
}

42. 接雨水

题目链接：https://leetcode-cn.com/problems/trapping-rain-water/

---

此题使用双指针对撞，有三个定理：

定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。

定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）

定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

                                   right_max
 left_max                             __
   __                                |  |
  |  |__   __??????????????????????  |  |
__|     |__|                       __|  |__
        left                      right

代码：

class Solution {
    public int trap(int[] height) {
        int length = height.length;
        if(length < 3){
            return 0;
        }
        // 注意初值的选取，前面做了特判，下标 0 和 len - 1 位置都不存雨水，因此这里有效
        // 在区间 [1, len - 2] 里计算存水量
        int left = 1, right = length - 2;
        int CurLeftHighest = height[0], CurRightHighest = height[length - 1];
        int res = 0;
        // 这里是等于，因为当 left == right 的时候，left(right) 这个位置的存水量还需要计算一下
        while(left <= right){
            int MinHeight = Math.min(CurLeftHighest, CurRightHighest);
            // 存水单位体积取决于较短的那个柱形的高度
            if(MinHeight == CurLeftHighest){
                // 大于当前，才可以存水
                if(MinHeight > height[left]){
                    res += MinHeight - height[left];
                }
                // 更新左边的柱形的最高高度
                CurLeftHighest = Math.max(CurLeftHighest, height[left]);
                // 指针右移
                left++;
            }else{
                if(MinHeight > height[right]){
                    res += MinHeight - height[right];
                }
                CurRightHighest = Math.max(CurRightHighest, height[right]);
                right--;
            }
        }
        return res;
    }
}