연속 부분 수열의 합 C++

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

※ 문제

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

 - 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.

   부분 수열의 합은 k입니다.
 - 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
 - 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

※ 나의 풀이

먼저 주어지는 vector는 정렬되어 있으므로 굉장히 마음이 놓인다.

처음에는 DFS로 접근을 했지만, 시간초과가 발생했다.

누적합이라는 것을 알게 돼서 이용하기로 했다.

그리고 투포인트를 이용하여 값을 찾기로 했다.

 

	int l = 0, r = 0, s = 0, e = 0;
	int length = 2147000000;
	int n = sequence.size();	// 5
	int sum = sequence[0];

	while (true)
	{
		// 합이 k와 같다면 기존에 저장되어 있는 길이와 비교하여 s, e 값 업데이트
		if (sum == k)
		{
			int tmp = r - l + 1;
			if (tmp < length)
			{
				s = l;
				e = r;
				length = tmp;
			}
		}
		
		// l, r이 vector의 끝에 위치하면 break;
		if (r >= n && l >= n) break;

		// sum이 k보다 작으면 r을 오른쪽으로 옮긴다.
		// 그 반대의 경우 l을 오른쪽으로 옮긴다.
		// r < n을 해주지 않으면 r값만 +돼서 while문이 끝나지 않을 수 있다.
		if (sum <= k && r < n)
		{
			r++;
			if (r < n) sum += sequence[r];
		}
		else
		{
			if (l < n) sum -= sequence[l];
			l++;
		}
	}