[이코테/투포인터/C++] 투포인터 설명, 구간 합 *

 

 

특정한 합을 가지는 부분 연속 수열 찾기

#include <bits/stdc++.h>

using namespace std;

int n = 5; // 데이터의 개수 n
int m = 5; // 찾고자 하는 부분합
int arr[] = {1, 2, 3, 2, 5}; // 전체 수열

int main(){
    int cnt = 0, intervalSum = 0, end = 0;
    for(int start = 0; start<n; start++) { // start를 차례대로 증가시키며 반복
        while(intervalSum < m && end < n){ // end를 가능한 만큼 이동시키기
            intervalSum += arr[end];
            end += 1;
        }
        if(intervalSum == m){ // 부분합이 m일 때 카운트 증가
            cnt += 1;
        }
        intervalSum -= arr[start];
    }
    cout << cnt << '\n';

    return 0;
}

 

구간 합

#include <bits/stdc++.h>

using namespace std;

int n = 5; // 데이터의 개수 n과 데이터 입력받기
int arr[] = {10, 20, 30, 40, 50};
int prefixSum[6];

int main(){
    // 접두사 합(Prefix Sum) 배열 계산
    int sumValue = 0;

    for(int i=0; i<n; i++){
        sumValue += arr[i];
        prefixSum[i+1] = sumValue;
    }

    // 구간 합 계산(세 번째 수부터 네 번째 수까지)
    int left = 3;
    int right = 4;
    cout << prefixSum[right] - prefixSum[left - 1] << '\n';

    return 0;
}