🖋️ 연속된 부분 수열의 합

# 문제 설명

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

=> 비내림차순 : 점점 증가하는 수열

• 조건
  

  • 기존 수열에서 임의의 두 인덱스의 원소와
    그 사이의 원소를 모두 포함하는 부분 수열

  • 부분 수열의 합은 k

  • 합이 k인 부분 수열이 여러 개인 경우
    길이가 짧은 수열을 찾기

  • 길이가 짧은 수열이 여러 개인 경우
    앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾기

• 매개 변수
  

  • 수열을 나타내는 정수 배열 sequence
  • 부분 수열의 합을 나타내는 정수 k

• 반환값
  

  • 위 조건을 만족하는 부분 수열의
    시작 인덱스와 마지막 인덱스를 배열에 담아 return

• 📢 제한사항

  • 5 ≤ sequence의 길이 ≤ 1,000,000
    • 1 ≤ sequence의 원소 ≤ 1,000
    • sequence는 비내림차순으로 정렬
      
      
  • 5 ≤ k ≤ 1,000,000,000
    • 1 ≤ sequence의 원소 ≤ 1,000
    • k는 항상 sequence의 부분 수열로 만들 수 있는 값

• 📰 입출력 예시

sequence	k	result
[1, 2, 3, 4, 5]	7	[2, 3]
[1, 1, 1, 2, 3, 4, 5]	5	[6, 6]
[2, 2, 2, 2, 2]	6	[0, 2]

• CODE

// 투 포인터 알고리즘
function solution (sequence, k) {
	const answer = [0, 1_000_000];
    
    // 두 개의 포인터 초기화
    let left = 0, right = 0;
    let sum = sequence[0];
  
    // 배열의 끝에 도달할 때
    while (right < sequence.length) {
       // k 값이 
       if (sum === k) {
          // idx 차이를 통한 길이 비교
          if (answer[1] - answer[0] > right - left) {
             answer[0] = left;
             answer[1] = right;
          }
          // 포인터 이동하면서 "+", "-" 하기
          sum -= sequence[left++];
          sum += sequence[++right];
       } else {
          // 포인터 이동 (right 는 +sum & left 는 -sum)
          sum = sum < k ? sum + sequence[++right] : sum - sequence[left++];
       }
    }
  
    return answer;
}

투 포인터 알고리즘

배열 및 목록 조작 문제, 특히 특정 기준을 충족하는
요소 쌍을 찾아야 할 때 사용

• 사용 경우
  • 쌍 검색
  • 중복 제거
  • 반전
  • 하위 문자열 or 배열
  • 이진 검색 응용 프로그램
    
    
• 사용 방법
  • 초기화 (두 개의 포인터로 시작)
  • 포인터 이동 (문제 조건에 따라 이동)
  • 조건 확인 (각 단계 충족하는지 확인)
  • 종료 (서로 만나거나 교차할 때 or 배열의 끝에 도달할 때)