프로그래머스 - 연속된 부분 수열의 합

문제 링크

제출 코드(통과)

using System;

public class Solution {
    public int[] solution(int[] sequence, int k) { 
        var i = sequence.Length - 1;
        var j = sequence.Length - 1;
        var sum = sequence[j];
        while (i >= 0 && sum != k)
        {
            if (sum > k)
            {
                if (i == j)
                {
                    i--;
                    j--;
                    sum = sequence[i];
                }
                else
                {
                    sum -= sequence[j--];
                }
            }
            else
            {
                sum += sequence[--i];
            }
        }

        while (i > 0 && sequence[i - 1] - sequence[j] == 0)
        {
            i--;
            j--;
        }
        
        return [i, j];
    }
}

비교적 간단한 투포인터 문제였다. 문제 조건 덕에 예외처리를 고려할 필요가 없어서 더욱 쉬웠다. 비내림차순 배열이므로 뒤에서부터 구간을 탐색하면 첫 번째로 발견한 부분 수열이 곧 최소 길이가 된다. 거기서 구간 길이를 유지하면서 합이 일정하도록 앞으로 이동할 수 있다면 (그러려면 배열 내부 및 그 앞 칸 원소의 값이 모두 같아야 한다.) 구간을 앞으로 한 칸씩 당긴다.