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

1.백트래킹(시간초과 = 통과안됨)

최악의 경우 O(n^2)

• 0부터 배열의 크기 N만큼 for문을 돌면서 index를 하나씩 올리면서 k와 같은지 체크
• 합이 k보다 크거나 이전에 저장한 배열의 길이보다 길면 탈출한다.

fun solution(sequence: IntArray, k: Int): IntArray {
    var n = sequence.size

    var ansStartIndex = 0
    var ansEndIndex =0
    var ansLength = Integer.MAX_VALUE
    for(i in 0 until n){
        var nowIndex = i
        var nowSum = sequence[i]

        while(true) {
            var len = nowIndex - i
            if (nowSum == k && ansLength > len) {
                ansStartIndex = i
                ansEndIndex = nowIndex
                ansLength = len
            }
            nowIndex++
            if (nowIndex >= n) break
            nowSum += sequence[nowIndex]
            if (nowSum > k) break
            if(len>ansLength) break
        }
    }
    var answer = intArrayOf(ansStartIndex,ansEndIndex)

    return answer
}

2. 투포인터(통과코드)

startIndex와 EndIndex를 0, 0으로 사작하여 sum값이 k보다 작으면 End를 한칸옮기고 k보다 크면 startIndex를 한칸옮긴다. O(n)

class Solution {
    var min = Integer.MAX_VALUE

    fun solution(sequence: IntArray, k: Int): IntArray {
    var n = sequence.size

    var ansStartIndex = 0
    var ansEndIndex = 0
    var sum = sequence[ansStartIndex]
    lateinit var answer :IntArray
    while (true) {
        if(sum == k) {
            var len = ansEndIndex-ansStartIndex
            if(min>len){
                min = len
                answer = intArrayOf(ansStartIndex, ansEndIndex)
            }
        }
        if (sum < k) {
            ansEndIndex++
            if(ansEndIndex>=n)break
            sum+=sequence[ansEndIndex]
        } else {
            sum-=sequence[ansStartIndex]
            ansStartIndex++
            if(ansStartIndex>=n) break
        }
    }

    return answer
    }
}