두 수의 합 3273

https://www.acmicpc.net/problem/3273

그냥 이중 for문 돌렸더니 시간초과 난다
시간복잡도가 1~N 까지 더한 수가 된다
수열크기가 100000 이니까 최악의 경우 시간복잡도는 Nlog(N) 정렬하는시간도 필요하니까 인듯하다

투포인터 강의를 살짝 보니 옛날에 풀었던 리트코드하면서 풀었던 기억이 났다
양쪽 끝에 왼쪽에 L 오른쪽에 R 포인터를 두고 L+R 이 x 보다 크면 R을 줄이고 작으면 L을 키우고..
같으면 둘다 R 줄이고 L키우고..

import java.io.*;
import java.util.Arrays;


public class Main
{
    //static int testcode = 0;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];

        String[] input = br.readLine().split(" ");
        for(int i = 0; i < arr.length; ++i)
        {
            arr[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(arr);

        int x = Integer.parseInt(br.readLine());
        int ans = 0;

        int lp = 0;
        int rp = arr.length-1;
        int sum = 0;
        while(lp < rp)
        {
            sum = arr[lp] + arr[rp];
            if(sum > x)
            {
                rp--;
            }
            else if(sum < x)
            {
                lp++;
            }
            else
            {
                rp--;
                lp++;
                ans++;
            }
            //testcode++;
        }

        System.out.println(ans);
        //System.out.println(testcode);
    }
}