[c++/알고리즘팁] 1차원배열의 부분합

1. 1차원 배열의 연속된 부분합을 구할때,
   1~N까지의 수 중, k개씩 더하는 부분집합을 더하라. 이런 문제를 풀때

for(int i=0; i<N-k; i++){
	for(int j=i; j<i+k; j++)
    	sum += number[j];
}

보통 위와 같이 for문을 사용하는 경우가 많을 것이다. 하지만 이것은 숫자가 커지면 시간초과로 오류가 발생된다.

=> 1차원 배열의 부분합을 구할 때, 시간복잡도를 n으로 구하기

for(int i=k; i<n; i++){
	sum = sum + (number[i] + number[i-k]);
}