【双指针题目】

美丽区间（滑动窗口）

美丽区间

滑动窗口模板：

int left = 0, right = 0;

while (right < nums.size()) {
    // 增大窗口
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.removeFirst(nums[left]);
        left++;
        //....更新
    }
}

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    	   public static void main(String[] args) {
	        Scanner scan = new Scanner(System.in);
	        //在此输入您的代码...
	        int slow=0,fast=0;
	        int min=(int)1e5+1;//最小区间
	        
	        int n=scan.nextInt();
	        int S=scan.nextInt();
	        int[]arr=new int[n];
	        for(int i=0;i<n;i++){
	            arr[i]=scan.nextInt();
	        }
	        int sum=0;//区间中的和
	        //fast 有解，slow 最优解
	        while(fast< n){
	           
	            	sum+=arr[fast];//扩大区间[slow,fast)，更新sum
	                fast++;               
	         
	            
	            while(sum-arr[slow]>=S){
	            	 sum-=arr[slow];//缩小区间[slow,fast)，更新sum
	                slow++;
	                
	                //跟新min
		            if(min>(fast-slow)){
		                min=fast-slow;
		            }
	            }            

	        }
	        if(min==(int)1e5+1) {
	        	System.out.println(0);
	        }else {
	        	System.out.println(min);
	        }
	        
	        
    }
}

合并数列（双指针的应用）

合并数列

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.ArrayList;
public class Main {
 public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt();
        int m=scan.nextInt();
        ArrayList<Integer>arr1=new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            arr1.add(scan.nextInt());
        }
        ArrayList<Integer>arr2=new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            arr2.add(scan.nextInt());
        }
        int l1=0,l2=0;
        int count=0;
        while(l1<arr1.size()&&l2<arr2.size()){
            if(arr1.get(l1)<arr2.get(l2)){
                //合并arr1中的l1,l1+1
            	arr1.set(l1, arr1.get(l1)+arr1.remove(l1+1));
            	count++;
            }else if(arr1.get(l1)>arr2.get(l2)) {
            	//合并arr2中的l2和l2+1
            	arr2.set(l2, arr2.get(l2)+arr2.remove(l2+1));
                count++;
            }else {
            	l1++;
            	l2++;
            }
        }
        System.out.println(count);
        scan.close();
    }
}

等腰三角形

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.ArrayList;
import java.util.Collections;
public class Main {
     public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int N=scan.nextInt();
        ArrayList<Integer> list1=new ArrayList<Integer>();
        for(int i=0;i<N;i++) {
        	list1.add(scan.nextInt());
        }
        ArrayList<Integer> list2=new ArrayList<Integer>();
        for(int i=0;i<N;i++) {
        	list2.add(scan.nextInt());
        }
        Collections.sort(list1);
        Collections.sort(list2);
        int j=0;
        int count=0;
        //两个指针指向两个数组，根据两边（腰）之和大于第三边（底）
        for(int i=0;i<N;i++) {
        	if(list1.get(i)*2>list2.get(j)) {
        		j++;
        		count++;
        	}
        }
     
      System.out.println(count);
        scan.close();
    }

}

全部所有的子序列

全部所有的子序列

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt();
       
        int[]arr=new int[n];
        HashSet<Integer> set=new HashSet<Integer>();
        for(int i=0;i<n;i++) {
            arr[i]=scan.nextInt();
            set.add(arr[i]);
        }
        int size=set.size();
        int len=(int)1e5;
        int l=0,r=0;//[)
        HashMap<Integer,Integer> window =new HashMap<Integer,Integer>();
        while(r<n) {
            //扩大窗口
            window.put(arr[r],window.getOrDefault(arr[r], 0)+1);
            r++;
            
            while(window.size()==size) {
                if(window.get(arr[l])==1){
                    break;
                }
                //可以缩小
                window.put(arr[l],window.get(arr[l])-1);
                l++;
                //更新
                if(len>r-l){
                    len=r-l;
                }
            }
        }
        if(len==100000){//注意：当序列为1 2 3 4 5 时，len=100000
        System.out.println(n);
        }else{
        System.out.println(len);
        }
        scan.close();
    }
}