尺取法

成为她曾经期待的样子 / 2023-05-12 / 原文

尺取法又叫双指针（two pointers）是竞赛中常用的优化基技巧，用来解决区间问题，操作简单。如果是单调区间也常用二分法

需要操作两个变量，可以用两个下标（指针）i，j 扫描区间。有二重循环，复杂度为O(n2)

for(int i=0;i<n;i++)
    for(int j=n-1;j>=0;j--)
        {
        }

实际上尺取法就是把二重循环变为一个循环，在这个循环中同时处理i,j，时间复杂都也从O(n2)变为O(n)

int i=0;
int j=n-1;
while(i<j)
{
    .....i++;
    .....j--;

}
//用for实现
for(int i=0;j=n-1;i<j;i--;j++)
{
}

在扫描方式中有两种扫描方式

(1)反向扫描：i和j反向相同，i从头到尾，j从尾到头。在中将相会。

(2)同向扫描。又称快慢指针。都是从头到尾，速度不同。

反向扫描经典例题：

输入n个整数放在a[]中，找出其中两个数，他们之和等于整数m所有整数都是int类型

输入样例

21 4 5 6 13 65 32 9 23

输出

5 23

 import java.sql.Array;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Scanner;
 public class Main{
     public static void main(String[]args)
     {
         Scanner input=new Scanner(System.in);
         int n= input.nextInt();

         int []ant=new int[n];
         for(int i=0;i< ant.length;i++)
         {
             ant[i]= input.nextInt();
         }
         int m= input.nextInt();
         Arrays.sort(ant);
         int i=0;int j=n-1;
         while(i<j)
         {
             int sum=ant[i]+ant[j];
             if(sum>m)
             {
                 j--;
             } else if (sum<m) {
                 i++;
 
             }
             else {
                 System.out.println(ant[i]+" "+ant[j]);
                 i++;
             }
         }
     }
 
 }

2 判断回文串

给定一个字符判定它是否是回文串

输入第一行输入一个整数n表示，表示测试实例个数。后面输入n个字符串

是回文输出yes,不是输出no

常规做法：

 import java.util.ArrayList;
 import java.util.Scanner;
 public class Main{
     public static void main(String[]args)
    {
         ArrayList<String> list=new ArrayList<>();
         Scanner input=new Scanner(System.in);
         int n= input.nextInt();
         while(n-->0)
         {
             String p= input.next();
             if(check(p))
             {
                 list.add("yes");
            }
             else{
                 list.add("no");
             }
         }
         for(int i=0;i< list.size();i++)
         {
             System.out.println(list.get(i));
         }
     }
     public static boolean check(String m)
     {
         StringBuilder st=new StringBuilder(m);
         st.reverse();
         int count=0;
         for(int i=0;i< st.length();i++)
         {
             if(st.charAt(i)!=m.charAt(i))
            {
                 return false;
             }
             else{
                 count++;
             }
         }
         if(count==m.length())
         {
             return true;
         }
         else{
             return false;
         }
     }
 }

寻找区间和，给定一个数组，在数组中找到一个区间，使得这个区间和等于S 输出起点和终点的位置

import java.util.Scanner;
public class Main{
    public static void main(String[]args)
    {
        Scanner input=new Scanner(System.in);
        int n= input.nextInt();
        int []ant=new int[n];
        for(int i=0;i<n;i++)
        {
            ant[i]= input.nextInt();
        }
        int s= input.nextInt();
        int i=0;
        int j=0;
        int sum=ant[0];
        while(j<n)
        {
            if(sum>=s)
            {
                if(sum==s)
                {
                    System.out.println(i+" "+j);
                }
                sum-=ant[i];
                i++;
                if(i>j&&i< ant.length)
                {
                    sum=ant[i];
                    j++;
                }
            }
            if(sum<s)
            {
                j++;
                if(j< ant.length)
                {
                    sum+=ant[j];
                }
                
            }
        }
    }

}

找相同数对，给定一串数，以及一个数字C要求计算A-B=C的数对的个数

import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[]args)
    {
        Scanner input=new Scanner(System.in);
        int n= input.nextInt();
        int c= input.nextInt();
        int []ant=new int[n+1];
        for(int i=1;i<=n;i++)
        {
            ant[i]= input.nextInt();
        }
        Arrays.sort(ant);
        long ans=0;
        for(int i=1,j=1,k=1;i<=n;i++)
        {
            while(j<=n&&ant[j]-ant[i]<c)
            {
                j++;
            }
            while(k<=n&&ant[k]-ant[i]<=c)
            {
                k++;
            }
            if(k-1>=1&&j<=n&&i<=n&&ant[j]-ant[i]==c&&ant[k-1]-ant[i]==c)
            {
                ans+=k-j;
            }
        }
        System.out.println(ans);
    }
}