2003번: 수들의 합 2

Memo

로직 설명

• 시작 포인터는 첫 번째 인덱스부터 시작합니다.
• 왼쪽 포인터는 원하는 값보다 현재 누적해온 값 보다 작은 합을 만들고 싶으면 증가시키고, 오른쪽 포인터는 원하는 값보다 현재 누적해온 값 보다 큰 합을 만들고 싶으면 증가시킵니다. (시간 복잡도 : O(N))

자료 구조

• array

코드 설명

while (right != N)
	{
		if (sum_val == M)
			ans++;
		if (sum_val > M)
		{
			sum_val -= A[left];
			left++;
		}
		else
		{
			right++;
			sum_val += A[right];
		}
	}

• "i번째 수부터 j번째 수까지의 합"에 초점을 맞춰봅니다.
• 오른쪽 포인터를 증가시켜 가며, 왼쪽 포인터와 오른쪽 포인터 사이 값들의 합이 M보다 크거나 같아질 때까지 증가시킵니다.
• M과 크기가 같아지면 count를 세줍니다.
• 만약 왼쪽 포인터와 오른쪽 포인터 사이 값들의 합이 M보다 커지면, 왼쪽 포인터를 증가시킵니다.
• 왼쪽 포인터를 증가시키면, 그 사이의 값들은 이전 값보다 무조건 작습니다.

어려웠던 부분 😭

• 투 포인터를 어떻게 적용할 것인지. 정렬을 하면 안되는데 계속 집착함.

개선할 부분 🤔