可恶。。居然碰到了周一面试没撕出最优复杂度的题

题目描述

• 难点在于时间复杂度O(n)，否则来个sort()还是很轻松的
  

思路 & 代码

• 一般来说，时间复杂度可以用空间复杂度来弥补：来选个数据结构吧！
• 显而易见，哈希表！K - V ：数组元素 - 以该元素为端点的序列的最长值
• 状态转移方程：now = left + right + 1
• 最优子结构：left & right
• put(i ,now) 只是为了 containsKey() 判断，状态转移还得看端点。

class Solution {
    public int longestConsecutive(int[] nums) { 
        int ans = 0;
        // 元素 - 连续值
        Map<Integer, Integer> hashmap = new HashMap<>();
        for(int i : nums){
            // 新值存入情况
            if(!hashmap.containsKey(i)){
                // 左边、右边的所处端点值
                int left = hashmap.get(i - 1) != null ? hashmap.get(i - 1) : 0;
                int right = hashmap.get(i + 1) != null ? hashmap.get(i + 1) : 0;
                int now = left + right + 1;
                ans = Math.max(now, ans);
                // 只存端点即可，具体原因可自己手写流程
                hashmap.put(i - left, now);
                hashmap.put(i + right, now);
                // 1. 为 containsKey 服务   2. 可能当前点就是端点
                hashmap.put(i, now);
            }
        }
        return ans;
    }
}
// 变式（返回答案数组）：维护一个index，随着ans更新而更新 index = i - left，最后按照 index & ans 创造新数组即可

变式题：返回答案数组

• 维护一个index，随着ans更新而更新 index = i - left，最后按照 index & ans 创造新数组即可

更新

• 经典空间换时间！注意 temp 也要 put 进去，因为 containsKey 要用！

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Map<Integer, Integer> hashmap = new HashMap<>();
        for(int temp : nums) {
            if(!hashmap.containsKey(temp)) {
                int left = hashmap.get(temp - 1) == null ? 0 : hashmap.get(temp - 1);
                int right = hashmap.get(temp + 1) == null ? 0 : hashmap.get(temp + 1);
                int now = left + right + 1;
                ans = Math.max(now, ans);
                hashmap.put(temp - left, now);
                hashmap.put(temp + right, now);
                hashmap.put(temp, now);
            }
        }
        return ans;
    }
}