연속된 부분 수열의 합

나의 코드

def solution(sequence, k):

    answer = []

    for i in range(len(sequence)):

        seq_sum = 0

        for j in range(i,len(sequence)):

            seq_sum+=sequence[j]

            if seq_sum==k:

                if len(answer)>0 and j-i < (answer[-1][1]-answer[-1][0]):

                    answer = []

                    answer.append([i,j])

                else:

                    answer.append([i,j])

               

                break

            elif seq_sum > k:

                break

    #print(answer)

    return answer[0]

solution([2, 2, 2, 2, 2], 6)

타임아웃 ㅋㅋㅋ 예상은 함 ㅋㅋ 이렇게 쉽게 풀릴리가 없지~~

def solution(sequence, k):

    answer = [0,0]

    seq_list = []

    sequence = sequence[::-1]

    for i in range(len(sequence)):

        seq_num = 0

        for j in range(i, len(sequence)):

            seq_num+=sequence[j]

            if seq_num == k:

                if len(seq_list)>0:

                    if j-i > (seq_list[0][1] - seq_list[0][0]):

                        break

                    else:

                        seq_list.append([i,j])

                else:

                    seq_list.append([i,j])

    #print(sequence)

    #print(seq_list)

    answer[0] = (len(sequence)-1) - seq_list[-1][1]

    answer[1] = (len(sequence)-1) - seq_list[-1][0]

    #print(answer)

    return answer

solution([1, 1, 1, 2, 3, 4, 5], 5)

역으로 풀어보았지만 타임아웃????

 

최종코드

def solution(sequence, k):

    answer = []

    seq_sum = 0

    l=0

    r=-1

    while True:

        if seq_sum < k:

            r+=1

            if r>=len(sequence):

                break

            seq_sum+=sequence[r]

        elif seq_sum>=k:

            seq_sum-=sequence[l]

            if l>=len(sequence):

                break

            l+=1

        if seq_sum==k:

            answer.append([l,r])

    answer.sort(key = lambda x: (x[1]-x[0], x[0]))

    #print(answer)

    return answer[0]

solution([1, 1, 1, 2, 3, 4, 5], 5)

후... 요즘 타임아웃에 너무 많이 걸린다 점점 갈수록 성격이 까다로워지는거 같음