尺取法详解

尺取法概念:双指针,算法竞赛中一个常用的优化技巧,操作简单、容易编程。

为什么尺取法能用来优化?

一把两种循环转化为一重循环，从而把复杂度从O(n2)提高到O(n)。

两种写法: for、while

for (int i = 0，j = n - l; i < j; i++， j--)      //i从头到尾，j从尾到头

{......}



int i = 0，j = n - 1;

while (i< j)     //i和j在中间相遇。这样做还能防止i、j越界//满足题意的操作

{   

i++;              //i从头扫到尾

j--;              //j从尾扫到头

}

 

 

例题:回文判定。

给定一个长度为n的字符串S，判断是否回文。

#include <bits/stdc++.h>

using namespace std;

int main(){



string s;

cin >> s;     //读字符串

bool ans = true;

int i = 0， j = s.size() - l;     //双指针



//反向扫描

while(i < j)

{

if(s[i] != s[j]){ ans = false; break; }  //不是回文

i++;j--;        //移动双指针

}



if(ans)cout << "Y"<< endl ;

else cout<<"N"<< endl;



return 0;

}

例题二：寻找区间和

题目描述:给定一个长度为n的数组a[]和一个数s，在这个数组中找一个区间，使得这个区间之和等于s。输出区间的起点和终点位置。

解析：

1. 初始值i=0、j=0，即开始都指向第一个元素a[0] ,定义sum是区间[i，j]的和，初始值sum = a[0]。
2. 如果sum等于s，输出一个解。继续，把sum减掉元素a[i]，并把i往后移动一位。
3. 如果sum大于s，让sum减掉元素a[i]，开把i往后移动一位。
4. 4.如果sum小于s，把j往后挪一位，并把sum的值加上这个新元素。

void findSum(int *a，int n,int s)

{

    int i = 0，j= 0;

    int sum = a[0];


    while(j < n){ //下面代码中保证 i<=j

        if(sum >= s){

        if(sum == s) printf("%d %d\n"， i，j);

        sum -= a[i];

        i++;
    
        if(i>j) {sum = a[i]; j++;}   //防止i超过j

      }



    if(sum< s){ j++;  sum += a[j];}

    }

}

例题三：锻造兵器

题目描述:有n块锻造石，第i块锻造石的属性值为ai。从这n块锻造石中任取两块来锻造兵器。

只有当两块锻造石的属性值的差值等于C，兵器才能锻造成功。请算算，有多少种选取锻造石的方案。

输入样例: 6 3

8 4 5 7 7 4

输出样例: 5

分析：任取两数，差值为C。样例中C=3，有5种方案:

8 5

4 7

4 7

7 4

7 4

#include <bits/stdc++.h>using namespace std;

const int N = 2e5+ 5;

int a[N];


int main (){


int n , c; cin >> n >> c;

for(int i= l ; i <=n ; i ++) cin >> a[i];

sort(a + l , a + l + n);     //排序

long long ans = 0;


/**

三指针:

i是主指针，从头到尾遍历n个数;

j、k是辅助指针，用于查找数字相同的区间[j，k]。

**/

for(int i=1，j=1,k=l ; i<= n ; i ++){

while(j <=n && a[j] - a[i]〈c ) j++;  //用j、k查找数字相同的区间

while(k <=n && a[k] - a[i]<= c) k++;  //区间[j, k]内所有数字相同

if(a[j]-a[i]==c && a[k-1]-a[i]==c && k-1>=1)  

ans += k - j;                     //统计数对

}


cout<<ans;

return 0;

}