第一級[1806]部分とC+解

白駿[1806]部分合
アイデア

[二重ポインタを使用

方法

二重ポインタを使用して長さを増やし、合値がSより大きいかどうかを確認します.
->S以上の場合、一番左の長さを減らしてもS以上でもよいので、開始点が1増加する
->Sより小さい場合は、終了点を1ずつ増やして値の個数

を増やす

終了点が範囲外、または開始点が終了点を超えた場合は、回答を停止して出力する.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>

using namespace std;

int main()
{
	int N, S; scanf("%d %d", &N, &S); 
	vector<int> numbers;

	for (int i = 0; i < N; i++)
	{
		int num; scanf("%d", &num);
		numbers.push_back(num);
	}

	//투포인터 사용
	int start = 0; int end = 0;

	int answer = 0;

	//첫번째 값은 미리 넣어둠
	int added_num = numbers[start];

	//start가 end를 넘어서면 잘못된 접근
	while (start <= end)
	{
		int length = end - start + 1;

		//만약 S보다 크면, start를 증가시켜줌
		if (added_num >= S)
		{
			if (answer == 0) answer = length;
			else if (answer > length) answer = length;
			added_num -= numbers[start];
			start++;
		}

		//만약 S보다 작으면, end를 증가시켜줌
		else if (added_num < S)
		{
			end++;
			if (end == N) break;
			added_num += numbers[end];
		}
	}

	printf("%d\n", answer);

	return 0;
}

評価
ダブルポインタを使うととても簡単な問題です
正解率が低いので疑問が生じたが,二重ポインタの概念を知らなければ,この問題は完全に解決できる.

勉強:一定の数列で「ダブルポインタ」を使うことを思い出す