题目分析
题目有一定的难度,如果想明白一个问题,则本题可以迎刃而解。下面给小伙伴们一些提示,其实本题就是在nums1中寻找与每个nums1元素对应的num2元素最接近的一个数。
题目描述的比较复杂,简单说来就是set方法第一个参数为key,将第二个参数value和第三个参数timestamp都放在其中,取出时只能看到时间戳之前的字符串,比如在key为foo,时刻为1时插入一个字符串bar,那么取出foo时在时刻1之后才能看到bar,在时刻1之前无法看到,同理如果在时刻4时放入bar2,那么在时刻4后bar2会替换bar,此后只能看到bar2了,但是在时刻1和时刻4之间只能看到bar。而且本题的时间戳时递增的,这一点非常重要,小伙伴们能够根据有序的线索得到哪些重要信息呢?
本题是连续子数组求和问题,子数组求和往往需要用到前缀和,因此可以使用sums记录前缀和,然后遍历起始和终止位置即可。这是本题的一般解法,时间复杂度为$O(n^2)$,空间复杂度为$O(n)$。但是有没有更精妙的解法呢?给小伙伴们提示一下,可以观察leetcode入坑题即第一题两数之和。
本题虽然是一个困难题,但是思路却很清晰,难点主要在于代码量和对字符串的处理操作。这个题目有点类似于括号匹配和带有括号的计算问题,都是栈的经典解法,这给小伙伴们一些提示,能否使用栈的思想解决本题呢?
最近的每日一题全部都是BFS,总是给小伙伴们介绍这类题型,可能会感觉到厌倦,但是集中训练也是非常有帮助的,而且最近这几题每一题的难度都较大,能做出这几道题目,有一种五岳归来不看山,黄山归来不看岳的感觉。