尺取り法(英語名：Two Pointer Technique)

はじめに(Two Pointer Technique)

尺取り法(英語名：Two Pointer Technique)についての解説記事です．Atcoder ABC130Dの問題で，尺取り法を使わないとテストコードが時間内に終わりません．そこで，尺取り法について学んだので，その内容をシェアしたいと思います．尺取り法の学習には，こちらの英語Web記事を参考にしました．

尺取り法(Two Pointer Technique)とは

1つの配列内の要素同士を比較する際，配列内のある2個の要素を示す「2個のポインタ(Two Pointer)」を使って比較すること．ポインタを使うことで，「要素比較の2回ループ」を「2個のポインタを動かす1回ループ」にすることができ，計算量を減らすことができる．それでは，Atcoder ABC130Dを「2回ループを使用する方法」と「尺取り法」を使う方法で解きます．

例題1

Atcoder ABC130Dの問題 D - Enough Array | AtCoder Beginner Contest 130 | AtCoder

「2回ループを使用」

配列の要素2つをi,jで表現して，2回ループしています．

import java.util.*;

public class Main{
    public static void main(String[] arg){
        Scanner scan =new Scanner(System.in);
        int n=scan.nextInt();
        int k=scan.nextInt();
        int[] A=new int[n];

        for(int i=0;i<n;i++){
            A[i]=scan.nextInt();
        }

        long sum=0;
        long ans=0;

        for(int i=0;i<n;i++){
            loop:for(int j=i;j<n;j++){
                if(j==i) {
                    sum=A[j];
                }
                else{
                    sum=sum+A[j];
                }
                if(sum>=k) {
                    ans=ans+n-j;
                    break loop;
                }
            }
        }
        System.out.print(ans);
    }
}

「尺取り法」

条件を満足する最小の和を持つ部分配列の，左と右の要素をpoint1,2でそれぞれ表現しています．

import java.util.*;
import java.lang.*;
import java.io.*;

public class ABC130D_2{
    public static void main(String[] arg){
        Scanner scan =new Scanner(System.in);
        int n=scan.nextInt();
        long k=scan.nextLong();
        long[] A=new long[n];

        for(int i=0;i<n;i++){
            A[i]=scan.nextLong();
        }

        long sum=0;
        long ans=0;
        int point2=0;

        for(int point1=0;point1<n;point1++){
            while(sum<k){
                if(point2==n) break;
                else{
                    sum+=A[point2];
                    point2++;
                }
            }
            if(sum<k) break;
            ans+=n-point2+1;
            sum-=A[point1];
        }
        System.out.print(ans);
    }
}

おわりに

例題を追加していきたいと思います．