-594. Longest Harmonious Subsequence – DeReK – Medium
简单难度的好题，我觉得不小心很容易跑偏的一道简单难度的题。先说说我自己的跑偏经历
首先这个是subsequence，所以其实原数组的顺序已经不重要了，或者说顺序根本不是考察的范围所能用得到的，所以我们要么可以排序再分析，要么就是利用HashMap来统计频率，这也是我知道的两个解法的始源
先说排序的算法：
- 排序了，然后怎么分析呢？一开始想的是直接遍历然后看是不是比前一个大一或者相等。我擦这么明显的错误都能犯？不是检测是不是递增，而是相差1的子数组相当于，否则连[1,2,3]这样的数组都不过测试。那就增加个临时变量表示之前的数字？还是不对因为这样还需要回溯，但是又回到哪里去呢？我们只设一个指针来遍历是不够的。那么我们用俩
- 两个指针其实就是我们最喜闻乐见的sliding window了。但是这个sliding window又稍微有些不一样。 一般siliding window是超出范围后结算的。但是这道题怎么说是"超出范围"呢？如果我们是决定num[right] 比 num[left] 大超过1是超出范围应该结算的话，那么这个test case就不对了：[1,1,1,4] 这个应该返回0，但是会被错误地返回3。 思来想去这道题的关键是当出现rigth比left的值大1的时候，我们才可以自信的说我们有harmonious subsequence，因为如果是1 1 1 1 或者 1，3，5，8都是不行的。
- 于是结算就不是发现窗口扩展不下去了再结算，而是每次只要有效都要结算。动态增加而不是最后结算。这样每次看到right比left的值大1就更新下res并right＋＋。其他如果right比left大于超过1。left＋＋，否则(其实也就是等于1) right＋＋。
再说HashMap，这个思路完全不一样，先遍历数组统计各数字的频率，然后再遍历一次来看每个数字是否其＋1和－1的数也在hashmap里，如果在就把俩人的freq的和跟res比，谁大要谁。然后将当前数字从map里删掉以免重复比较。
这个思路很简单而且只需要O(n)的时间和O(n)的space。但是其运行速度却比上一个要慢了50％，为什么呢？我能想到的就是hashmap的查找和增删时间的消耗。
Read full article from -594. Longest Harmonious Subsequence – DeReK – Medium
No comments:
Post a Comment