字节10-8 糖葫芦

题目描述：
小红想用山楂制作糖葫芦，糖葫芦是一串字符串，比如abc，然后a代表甜味为0，b代表1，c代表2，……（以此类推）。然后要取一段连续的糖葫芦（连续子数组），它的甜味就是所有子数组值之和。请问第k大的糖葫芦甜味是多少？p.s. 糖葫芦如果倒着来和另一串相同的话，算作同一个（不允许存在逆序后相同的连续子串）。如果不存在第k个，就输出-1。

输入输出分为别：输入第一行是n k，第二行是糖葫芦；输出则是第k甜的连续糖葫芦有多甜。

Example
输入：
3 4
abc

输出:
1

输入:
3 4
aba

输出:
0

n大概封顶200

这是字节最后一道笔试题，其实不算难道没法写，（其实字节难得很均匀，都蛮难的，没有特别简单的题），我当时比较慌乱，调了很多次bug（而且居然不允许用本地IDE不然算跳出界面）只过了50%。我当时是图快挣点分就做别的，就直接用双指针+一个数组存现有的子串了，这其实会引起非常多的重复计算。所以后来自己复盘想了一下其实可以用字典树trie代替普通的列表用来争取时间。

代码：

n,k = list(map(int,input().strip().split()))
s = input().strip()

trie = dict()
trie['end'] = False

def find(tree,s):
    if not s:return tree['end']
    if s[0] not in tree:return False
    else:return find(tree[s[0]],s[1:])

def build(tree,s):
    if not s:
        tree['end'] = True
        return
    if s[0] not in tree:
        tree[s[0]] = dict()
        tree[s[0]]['end'] = False
    build(tree[s[0]],s[1:])
      
arr = [ord(x)-ord('a') for x in s]
presum = [0]
for x in arr:presum.append(presum[-1]+x)
n = len(arr)
res = []
for i in range(n):
    for j in range(i+1,n+1):
        if not find(trie,arr[i:j]) and not find(trie,arr[i:j][::-1]):
            build(trie,arr[i:j])
            res.append(presum[j]-presum[i])

res.sort(reverse=True)
if k>len(res):print(-1)
else:print(res[k-1])

时间复杂度大概是O(n^3)吧，双指针就是n^2了，每一次查找了建字典树就是等同于遍历一遍子串本身，所以一共n^3，应该不会超时。