javascript - 在 GenomicRangeQuery Coditlity 挑战中克服时间复杂性的问题

Question

我正在执行 GenomicRangeQuery [链接到任务]：https ://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/我得到时间复杂度 O(N * M)。

我不确定究竟是代码的哪一部分导致了它。目前我正在学习时间复杂度，所以我欢迎任何建设性的见解。

这是我的解决方案：

function solution(S, P, Q) {
   const factors = {
       A: 1,
       C: 2,
       G: 3, 
       T: 4
   }

   const A = S.split("")

   const result = []

   let prevRangeValues = {};

   for(let i = 0; i < P.length; i++) {
       const start = P[i]
       const end = Q[i] + 1

       if (prevRangeValues[`${start}-${end}`] === undefined) {
            const section = A.slice(start, end)
            prevRange = [start, end]

            const smallest =  Array.from(new Set(section)) 
                .sort()[0]

            result.push(factors[smallest])
            prevRangeValues[`${start}-${end}`] = factors[smallest]
       } else {
        result.push(result[result.length - 1])
       }         
   }

   return result
}

标签： javascriptecmascript-6