[伯俊]#13144 Unique Numbersリスト



質問する


長さNの数列が与えられると、数列から1つ以上の連続する数列が抽出され、同じ数列が複数回現れると、その数列を解くプログラムが作成される.

入力


第1行は、数列の長さNを与える.(1 ≤ N ≤ 100,000)
2行目には、数列を表すN個の整数が与えられる.数列に表示される数字はいずれも1以上100000以下です.

しゅつりょく


条件を満たす数を出力します.

入力例1

5
1 2 3 4 5

サンプル出力1

15

入力例2

5
1 2 3 1 2

サンプル出力2

12

入力例3

5
1 1 1 1 1

サンプル出力3

5

に答える


この問題は二重ポインタで解くことができる.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] arr = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        long ans = 0;

        HashSet<Integer> visited = new HashSet<>();   //숫자 체크할 해쉬셋
        int left = 0;
        int right = 0;

        while(true) {
            if(right==N) {
                if(left==N) break;

                else {
                    ans += (right-left);
                    left++;
                }
            }

            else if(!visited.contains(arr[right])) {    //포함안된 숫자면 포인터 늘림
                visited.add(arr[right]);
                right++;
            }

            else {
                ans += (right-left);          //이미 포함된 숫자면 다 더해주고 시작 idx 늘림
                visited.remove(arr[left]);
                left++;
            }
        }

        System.out.println(ans);
    }
}