【题目】

【分析】

这个题难倒是不难，关键要效率。

【方法一：使用HashMap】

首先遍历一遍数组，将<num, num出现次数>保存到HashMap中。

然后遍历HashMap中的key，如果key+1也存在。就可以求出key和key+1对应的值之和。

代码：

结果：

我看到别人用这个方法，最好的效果能到46ms。我没有跑出来。而且我把别人46ms的代码拿过来，我还是跑了80多ms。

我猜测可能是leetCode改了测试用例之类的吧。

【方法二：双指针】

先排序，然后用双指针遍历。

比如：排序后为1 1 2 2 2 3 3 5 7

1. 初试两个指针i、j，开始时都指向0。

2. num[j]==num[i]，j往后移：

3. num[j]==num[i]，j往后移：

4. num[j]==num[i]+1，更新最大长度。res = max(res, j-i+1 ) = 3。j往后移：

5. num[j]==num[i]+1，更新最大长度。res = max(res, j-i+1 ) = 4。j往后移：

6. num[j]==num[i]+1，更新最大长度。res = max(res, j-i+1 ) = 5。j往后移：

7. num[j]>num[i]+1，i往后移：

8. num[j]>num[i]+1，i往后移：

9. num[j]==num[i]+1，更新最大长度。res = max(res, j-i+1 ) = 5。j往后移：

10. num[j]==num[i]+1，更新最大长度。res = max(res, j-i+1 ) = 5。j往后移：

11. num[j]>num[i]+1，i往后移：

12. num[j]>num[i]+1，i往后移：

13. num[j]>num[i]+1，i往后移：

14. num[j]>num[i]+1，i往后移：

15. num[j]>num[i]+1，i往后移：

16. num[j]==num[i]，j往后移：

17. num[j]>num[i]+1，i往后移：

18. num[j]==num[i]，j往后移：

19. 结束。

代码：

简化一下：

结果：

虽然方法二的结果比方法一要好，但是并不一定。方法一的时间复杂度为o(n)，方法二的时间复杂度为o(nlogn)。可能是由于测试事例的问题，或者由于方法一取数置数的操作太多，导致运行慢了。但是基因决定了方法一优于方法二。

通过128，我们也看到这个奇怪的现象。o(n)的算法慢，先排序统计的o(nlogn)的算法快。