一. 题目

二. 思路

1. 记忆化搜索

• 现用HashSet存储所有数，平均查询O(1)

• 记忆化搜索n->n-1->....，避免重复查找。

2. 哈希表

三. 代码

1. 记忆化搜索

class Solution
{
    Set<Integer> ns = new HashSet<>();
    Map<Integer, Integer> f = new HashMap<>();

    int dfs(int x)
    {
        if (f.containsKey(x)) return f.get(x);

        int len = 1;
        if (ns.contains(x - 1))
            len += dfs(x - 1);
        f.put(x, len);
        return len;
    }

    public int longestConsecutive(int[] nums)
    {
        for (Integer num : nums)
            ns.add(num);
        int ans = 0;
        for (Integer num : nums)
            ans = Math.max(ans, dfs(num));
        return ans;
    }
}