• 👑专栏内容：算法学习随笔
• ⛪个人主页：子夜的星的主页
• 💕座右铭：日拱一卒，功不唐捐

目录

• 一、前言
• 二、左右指针（双向奔赴）
• • 1、定义
  • 2、回文检查
  • 三、快慢指针（你追我赶）
  • • 1、定义
    • 2、美丽的区间
    • 四、后记

      ---

      一、前言

      双指针法又称尺取法，顾名思义，在区间操作时，使用两个指针同时遍历区间，从而实现高效操作。两个指针，就像是一男一女，他们遍历区间的过程，又何尝不像是一对男女彼此追求爱情的过程呢？

      接下来一起学习双指针的恋爱过程。

      

      二、左右指针（双向奔赴）

      我渴望能见你一面，但请你记得，我不会开口见你。这不是因为我骄傲，你知道我在你面前毫无骄傲可言，而是因为，唯有你也想见我的时候，我们见面才有意义。——《越洋情书》西蒙·波伏娃

      1、定义

      左右指针，顾名思义，指针i与指针j，一个在左边，一个在右边。

      两个指针的遍历方向相反，一个指针i从左往右，一个指针j从右往左。最终它们会在中间相会。

      左右指针认为：真正的爱是双向奔赴，不论双方的差距有多大，距离有多远，只要双向奔赴，最终必将走到一起 ~

      

      2、回文检查

      【题目描述】 给定一个长度为 n 的字符串 S。请你判断字符串S 是否回文。

      【输出描述】 输入仅1行包含一个字符串S。 1 ≤ S ≤ 1 0 6 1≤ S≤10^6 1≤S≤106，保证S只包含大小写、字母。

      【输出描述】 若字符串S为回文串，则输出 Y，否则输出 N。

      【参考样例】 输入：abcba 输出：Y

      回文：正读和倒读意义相同的，称为“回文”

      #include 
      using namespace std;
      int main()
      {
          string s;   
          cin >> s;                  //（1）读取字符
          size_t n = s.size();       //（2）获取字符长度
          int i = 0; int j = n - 1;  //（3）双指针（一左一右）
          while (i < j)             
          {
              if (s[i] != s[j])  	 //（4）判断回文
              {
                  cout << "N";    
                  return 0;      	 //（5）结束程序
              }
              i++; j--;           //（6）移动指针
          }
          cout << "Y";
          return 0;
      }
      

      

      这道题不难，有很多种方法。但是双指针是用起来最爽的。通过这道题，我们也可以大致看出来这双向奔赴的爱情大致的模样。

      	int i = 0;int j =n - 1;
          while (i < j)             
          {   
              check(i, j);  //检查题目条件
              i++; j--;    //移动指针，i从头到尾，j从尾到头
          }
      

      三、快慢指针（你追我赶）

      不要追求幸福，而要幸福地追求。过程中的享受与快乐才是我们的需求。

      1、定义

      快慢指针，顾名思义，指针i与指针j，在同一方向，但是指针i和指针j的遍历速度不一样。恰恰是因为i和j的速度不同，它们之间会产生一个大小可变的滑动窗口，而这个窗口，正是它们幸福的来源。

      快慢指针认为：真正的爱恰恰是你追我赶时产生的窗口期，如果没有这种不断追赶的过程，爱将会变的无趣，这个就是爱的魅力 ~

      

      2、美丽的区间

      【题目描述】 给定一个长度为 n n n的序列 a 1 , a 2 , ⋅ ⋅ , a n a_1,a_2,··,a_n a1​,a2​,⋅⋅,an​和一个常数 S。对于一个连续区间如果它的区间和大于或等于 S ,则称它为美丽的区间。对于一个美丽的区间，如果其区间长度越短，它就越美丽。请你从序列中找出最美丽的区间。

      【输入描述】 第一行包含两个整数，S,其含义如题所述。接下来一行包含几个整数，分别表示 a 1 , a 2 , ⋅ ⋅ , a n a_1,a_2,··,a_n a1​,a2​,⋅⋅,an​ 。

      10 ≤ N ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 4 , 1 ≤ S ≤ 1 0 8 10≤N≤10^5,1≤a_i≤10^4,1≤S≤10^8 10≤N≤105,1≤ai​≤104,1≤S≤108。

      【输出描述】 输出共一行，包含一个整数，表示最美丽的区间的长度。若不存在任何美丽的区间，则输出 0 。

      【参考样例】

      输入：

      5 6
      1 2 3 4 5
      

      输出：

      2
      

      #include 
      #include
      using namespace std;
      int a[101000];
      int main()
      {
      	int n, s;
      	cin >> n >> s;
      	for (int i = 0; i < n; i++)
      		cin >> a[i];
      	int sum = 0, ans = 1e8;
      	int i = 0, j = 0;
      	while (i < n)    //遍历整个列表
      	{ 
      		if (sum < s)   //若区间和小于s
      		{
      			sum += a[i]; //区间和一直加
      			i++;         //i指针右移
      		}
      		else
      		{
      			ans = min(i - j, ans); //记录短的区间长度
      			sum -= a[j];          //区间和减
      			j++;                  //j指针右移
      		}
      	}
      	if (ans == 1e8)         //答案不存在
      		cout << 0;
      	else
      		cout << ans;         
      	return 0;
      }
      

      

      四、后记

      1、当出现有序数组或者题目具有单调性（任意一个指针的增加，条件满足与否只会出现对或错这两种情况）时，应该优先想到使用左右指针来减少遍历的时间。

      2、当出现前缀和、区间的时候，可以想到使用快慢指针。

      注意：篇幅有限，本文只是介绍了双指针最基础的定义和最简单的题目，双指针很多题远比本文出现的题目难。大家可以点个关注，等有时间我再继续更。

      📢📢📢📢📢📢

      💗 你正在阅读 【子夜的星】 的 算法笔记

      👍 阅读完毕，可以点点小手赞一下

      🌻 发现错误，直接评论区中帮我指正吧