2중 for문으로 O(n^2)으로 해결할 문제를 이 두가지 알고리즘을 잘 사용하면 O(n)으로 해결할 수 있음

이중 포인터

0302번

package Section3;
import java.util.*;

public class problem0302RE {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int num1 = in.nextInt();
        int[] arr1 = new int[num1];
        for (int i=0;i<num1;i++){
            arr1[i]=in.nextInt();
        }
        int num2 = in.nextInt();
        int[] arr2 = new int[num2];
        for (int i=0; i<num2; i++){
            arr2[i]=in.nextInt();
        }

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int p1 = 0;
        int p2 = 0;

        ArrayList<Integer> answer = new ArrayList<>();

        while (p1<num1&&p2<num2){
            if (arr1[p1]==arr2[p2]) {
                answer.add(arr1[p1]);
                p1++;
                p2++;
            }
            else if (arr1[p1]>arr2[p2]){
                p2++;
            }
            else {
                p1++;
            }

        }

        for (int i=0; i<answer.size(); i++){
            System.out.print(answer.get(i)+" ");
        }




    }
}

포인터 변수 2개를 사용해서 비교하는 방식
합병정렬에서 정렬하는 과정에서 사용하는 방식

sliding window

0303번

package Section3;
import java.util.*;
public class problem0303RE {
    //2중for문으로 풀면 O(n^2)인데 sliding window로 풀면 O(n)
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();
        int[] arr = new int[input1];
        int sum = 0;
        for (int i=0; i<input1; i++){
            arr[i]=in.nextInt();
            if (i<input2) {sum+=arr[i];}
            }

            int max = sum;
            for (int i=input2; i<input1; i++){
                sum = sum-arr[i-input2]+arr[i];
                if (max<sum) {max=sum;}
            }

            System.out.println(max);






        }
}

window 크기를 정해놓고 한칸씩 이동하면서 그 부분만 보는 방식
이렇게 안하면 2중 for문으로 돌아야 함