연속된 부분 수열의 합

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

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

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

import java.util.*;

public class Main {
    public static void main(String[] args) {

        int[] sequence = {1, 1, 1, 2, 3, 4, 5};
        int k = 5;

        var reuslt = solution(sequence, k);

        System.out.println(Arrays.toString(reuslt));
    }

    public static int[] solution(int[] sequence, int k) {

        LinkedList<BM> list = new LinkedList<>();
        LinkedList<BM> list2 = new LinkedList<>();
        LinkedList<BM> sw;

        BM resultBM = null;

        int mm = k;
        for (int i = 0; i < sequence.length; i++) {

            while (!list.isEmpty()) {
                BM temp = list.pop();
                temp.value += sequence[i];
                temp.size++;

                if (temp.size >= mm) {
                    continue;
                }

                if (temp.value < k) {
                    list2.add(temp);
                }
                if (temp.value == k) {
                    mm = temp.size;
                    temp.end = i;
                    resultBM = temp;
                }
            }

            var newBM = new BM(i, sequence[i]);

            if (newBM.value == k) {
                newBM.end = i;
                newBM.size = newBM.end - newBM.start;
                resultBM = newBM;
                break;

            }

            if (newBM.value < k) {
                list2.add(newBM);
            }
            
            sw = list;
            list = list2;
            list2 = sw;

        }

        int[] result = {resultBM.start, resultBM.end};

        return result;
    }
}

class BM {
    int start;
    int end;
    int value;

    int size;

    public BM(int start, int value) {
        this.start = start;
        this.value = value;
    }

}

슬프게도 시간초과

이후 슬라이딩 윈도우 로 해결

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {

        int[] sequence = {1, 1, 1, 2, 3, 4, 5};
        int k = 5;

        var result = solution(sequence, k);

        System.out.println(Arrays.toString(result));
    }

    public static int[] solution(int[] sequence, int k) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        int[] result = new int[2];

        while (right < sequence.length) {
            sum += sequence[right];

            while (sum > k && left <= right) {
                sum -= sequence[left];
                left++;
            }

            if (sum == k && (right - left + 1) < minLength) {
                minLength = right - left + 1;
                result[0] = left;
                result[1] = right;
            }

            right++;
        }

        return result;
    }
}