Baekjoon - Sum of Numbers 2

Baekjoon : Sum of Numbers 2

Description

Given an array A of size N , return the number of cases in which A's i-th index to j-th index (i.e - A[i]+A[i+1]+…+A[j-1]+A[j]) equals input M

Restriction

N(1≤N≤10,000), M(1≤M≤300,000,000), A[x] < 30,000

Example 1

Input

4 2 // N = 4 , M = 2
1 1 1 1

Output

3

Example 2

Input

10 5
1 2 3 4 2 5 3 1 1 2

Output

3
// 2 + 3
// 5
// 3 + 1 + 1

Approach

If taking a naive approach, brute force might be the solution by iterating through every elements. However, in order to avoid O(n^2), two pointer algorithm must be implemented for the time complexity of O(N)

Solution (C++)

#include <iostream>
using namespace std; 

int N, M;
int K;
int A[10000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    int result = 0, sum = 0, left = 0, right = 0;

    while (1)
    {
        if (sum >= M)
        {
            sum -= A[left++];
        }
        else if (right == N)
        {
            break;
        }
        else
        {
            sum += A[right++];
        }

        if (sum == M)
        {
            result += 1;
        }
    }

    cout << result;

    return 0;
}