CSES 2. Subarray Sums II (1661)

출처: https://cses.fi/problemset/task/1661

---

문제 설명

Given an array of n integers, your task is to count the number of subarrays having sum x.

입력 

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a_1,a_2,…,a_n : the contents of the array.

출력 

Print one integer: the required number of subarrays.

입력 예

5 7
2 -1 3 5 -2

출력 예

2

제약조건

• 1 <= n <= 2x10^5
• −10^9 <= x, a_i <= 10^9

---

문제 풀이 

배열을 입력 받아서, 그 값들을 누적하고, 이렇게 만들어진 합들을 key 로 하는 map을 만든다. 

pre_sum[i] == tSum or pre_sum - tSum == pre_sum[j] 인 경우가 우리가 찾는 sub-array가 된다.

이런 경우들을 세서 출력한다.

프로그램 내용

...
    vector <long> num_arr(nNum);
    vector <long long> sum_arr(nNum+1,0);

    for(int idx=0; idx < nNum; ++idx)
        cin >> num_arr[idx];
        sum_arr[idx+1] = sum_arr[idx] + num_arr[idx];

    map <long long, int> m_map;
    m_map[0] = 1;

    for (int idx=0; idx < nNum; ++idx) /// update map with array pre-sum
        m_map[sum_arr[idx+1]]++;

    long long answer = 0;
    for (int idx=0; idx < nNum; ++idx) 
        answer += m_map[sum_arr[idx+1] - tSum]; /// if pre_sum == tSum or diff of pre_sum == tSum
...

 

Sorting and Searching ( link )