最长连续序列[扩散法+空间换时间]

前言

空间换时间核心是为了降低时间复杂度，但有时候是解题的关键，毕竟时间有限（先双指针一样）。
典型的空间换时间就是数组/数组hash/hash。
本文通过最长连续序列来感受空间换时间，并练习扩散法。

一、最长连续序列

二、扩散法+空间换时间

package everyday.medium;

import java.util.HashSet;
import java.util.Set;

// 最长连续序列
public class LongestConsecutive {
    
    /* target：找到里面最长连续数字，如果排个序，直接O(n)遍历一遍记录到最长即可。 但是时间复杂度要求O(n),所以只能空间换时间,先用hash存起来，方便后面快速查找(以扩散法查找)。 */
    public int longestConsecutive(int[] nums) {
    
        // 特殊情况，特殊处理。
        if (0 == nums.length) return 0;
        Set<Integer> set = new HashSet<>();
        // 准备工作，记录所有元素，并赋初值为1，表示连续个数1。
        for (int n : nums) if (!set.contains(n)) set.add(n);
        // 遍历nums，求相邻的元素的总连续度。
        int ans = 1;
        // 扩散法，每个值最多被访问两次，一次有，一次无。
        for (int n : nums) {
    
            // 没有用过的数字，才从两边扩散开来。
            if (set.contains(n)) {
    
                // 开始往两边扩散，扩散法。
                int len = 1;
                int left = n, right = n;
                while (set.contains(--left)) {
    
                    ++len;
                    set.remove(left);
                }
                while (set.contains(++right)) {
    
                    ++len;
                    set.remove(right);
                }
                // 取每次能扩散的最大长度。
                ans = Math.max(ans, len);
            }
        }
        return ans;
    }
}

总结

1）空间换时间
2）扩散法

参考文献

[1] LeetCode 最长连续序列