[数据结构与算法]零基础学算法100天第8天——双指针（基础算法）

??大家好啊，我是执梗。许久未更新，今天补充一篇很常用的算法教学——双指针。掌握好一门算法，不仅要熟练写出模板，而且能识别出应用的场景，遇见了却想不到要使用它，那说明火候不够。我的文章将从各个习题进行讲解。

1.什么是双指针？

??双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。
??双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。
??它很容易帮助我们将某些暴力的做法将复杂度降低一个度，从而达到过题的目的。

2.维护区间信息

??双指针最直观的使用就是维护一段区间的信息，特别是一段具有单调性的区间，对于新增和删除元素都很方便处理的信息，比如正数的区间和或者积等。

1.乘积小于 K 的子数组

??给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
原题链接: 乘积小于 K 的子数组

2.解题思路

• $(1)$由于nums全都是正整数，所以我们可以考虑暴力做法，对于每一个下标i我们固定为某个子数组的左端点，然后遍历它右边的所有下标j，看有多少区间$[i,j]$内的乘积是小于k的。很显然这样的复杂度为$O(n^2)$无法通过。
• $(2)$对于乘积，很显然我们具有这样一个性质，当区间$[j,i]$的乘积此时小于k，那么对于所有区间$[j+1,i]、[j+2,i]、......[i?1,i]$的乘积都是小于k的，那么很明显以i为右端点符合条件的答案个数为i-j+1个。
• $(3)$思路2中，j是每个i最左能到达的距离，也就是在当j再左移动一格就无法满足题意，也就是区间$[j?1,i]$乘积不小于k。当然j此时不能为0。
• $(4)$此时考虑到最核心的地方，当i指针往右移动时，左指针j会如何变化？对于区间$[j,i]$此时变成了$[j,i+1]$，由于$a[i+1]>=1$，所以乘积只会变大或者不变，那么为了保证区间内乘积一定小于k，我们的 $j$ 要么只能向左移动除掉 $a[j]$ 的值或者不动。也就是说，随着 $i$ 指针的右移，左指针 $j$ 也随之右移或不移，因此两指针的移动具有单调性。
• $(5)$我们只需要每次移动右指针 $i$ 后，将左指针 $j$ 移动符合的位置，然后统计答案，每个数作为右端点的子数组，这样就能不重不漏的统计出所有符合条件的子数组。具体实现见代码注释。

3.模板代码

class Solution {
    public int numSubarrayProductLessThanK(int[] a, int k) {
        int n=a.length;
        int res=0;
        long ans=1;
        for(int i=0,j=0;i<n;++i){
            ans*=a[i];//循环里i右移了，所以加上a[i]的值
            while(j<i&&ans>=k){ //移动的条件是ans>=k，当然也要保证j<i
                ans/=a[j]; //去掉a[j]的值
                j++;//左指针个右移
            }
            if(ans<k) res+=i-j+1;//注意单a[i]一个数也可能大于k，需要判断
        }
        return res;
    }
}

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& a, int k) {
        int n=a.size();
        long long ans=1;
        int res=0;
        for(int i=0,j=0;i<n;++i){
            ans*=a[i];
            while(j<i&&ans>=k){
                ans/=a[j];
                j++;
            }
            if(ans<k) res+=i-j+1;
        }
        return res;
    }
};

时间复杂度 : 每个点最多被左指针和右指针分别遍历一遍，时间复杂度为$O(n)$。

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

??给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。$(n<=1e5,a[i]<=1e5)$

2.解题思路

• $(1)$本题与上一轮的区别在于，维护区间的信息不同以及求解的答案是最长的区间而不是总的区间数量。但本质上在维护的同时都双指针都具有单调性移动。
• $(2)$当 $i$ 指针右移时，区间的值将会加入 $a[i]$ ，如果此时区间内已经存在$a[i]$且它的下标为$k$，那我们的左指针必须向右移动，不断移除区间内的元素，直到移动到 $k+1$这个下标，保证区间内不存在重复元素，此时区间长度为i-j+1。
• $(3)$对于每一个数我们都作为区间的右端点 $i$，通过双指针去找到它的最远左端点 $j$ ，使得满足区间$[j,i]$不存在重复元素，对所有区间长度取最大则为答案。对于维护区间存在哪些数，我们自然想到使用哈希表，因为数值最大为$1e5$，我们可以使用数组哈希更快，如果数值为$1e9$那就需要使用哈希表了。

3.模板代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int cnt[N],a[N];
int main() 
{
	ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);	
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    int ans=0;
	for(int i=1,j=1;i<=n;++i){
		cnt[a[i]]++;
		while(j<i&&cnt[a[i]]>1){
			cnt[a[j]]--;
			j++;
		}
		ans=max(ans,i-j+1);
	}
	cout<<ans<<'\n';
    return 0;
}

import java.util.Scanner;
public class Main {
    static int N=100010;
    static int[] a=new int[N];
    static int[] s=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for (int i=0;i<n;++i) a[i]=sc.nextInt();
        int res=0;
        for (int i=0,j=0;i<n;++i){
            s[a[i]]++;
            while (s[a[i]]>1){
                s[a[j]]--;
                j++;
            }
            res=Math.max(res,i-j+1);
        }
        System.out.println(res);
    }
}

3.子序列匹配

??此类问题需要将字符串 $s$ 与 $t$ 进行匹配，判断 $t$ 是否为$s$ 的子序列。解决这种问题只需先将两个指针一个 $i$ 放在 $s$ 开始位置，一个$j$ 放在 $t$ 开始位置，如果 $s[i]==t[j]$ 说明 $t$ 的第 $j$ 位已经在 $s$ 中找到了第一个对应，可以进而检测后面的部分了，那么 $i$ 和 $j$ 同时加一。如果上述等式不成立，则 $t$ 的第 $j$ 位仍然没有被匹配上，所以只给 $i$ 加一，在 $s$ 的后面部分再继续寻找。最后，如果 $j$ 已经移到了超尾位置，说明整个字符串都可以被匹配上，也就是 $t$ 是 $s$ 的一个子序列，否则不是。

1.通过删除字母匹配到字典里最长单词

??给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

2.解题思路

• $(1)$对于每个字符我们都可以暴力匹配一下，为了找到最长且字典序最小的，我们考虑先将字符串排序后倒着进行匹配。

3.模板代码

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
 		 sort(dictionary.begin(), dictionary.end());
 		 int mx = 0, r = 0;
  		 string ans = "";
  for (int i = dictionary.size() - 1; i >= 0; i--) {
   		 r = 0;
   		 for (int j = 0; j < s.length(); ++j) {
     		 if (s[j] == dictionary[i][r]) r++;
   			 }	
 		   if (r == dictionary[i].length()) {
  		   if (r >= mx) {
    		    mx = r;
      			  ans = dictionary[i];
     	 }
   		 }
 	 }
 	 return ans;
	}
};

4.序列有序性

??这是双指针最常见的运用场景，序列的有序性通常是我们能使用双指针的显著特征。而且这类问题也可以通过二分解决，但是二分的复杂度会带多一个$log$，而且代码不如二分简洁。不过二分做法一般也不会被卡，属于是看个人习惯。

1.二分之和||-输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

2.解题思路

• $(1)$由于查找的是两个不同位置的数，且一个较大一个较小，我们可以使用两个指针分别指向一大一小的元素，一个指向头部，一个指向尾部，分别为 $j$ 和 $i$ ，当$a[i]+a[j]>target$ 时，说明较大值偏大我们让 $i$ 左移一格，如果$a[i]+a[j]<target$ 说明较小值偏小，我们让 $j$ 右移一格。直到判断到符合的情况。

3.模板代码

class Solution {
public:
    vector<int> twoSum(vector<int>& a, int target) {
        int n=a.size();
        int l=0,r=n-1;
        vector<int> ans;
        while(l<r){
            if(a[r]+a[l]>target) r--;
            else if(a[r]+a[l]<target) l++;
            else{
                ans.push_back(l+1);
                ans.push_back(r+1);
                return ans;
            }
        }
        return ans;
    }
};

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