LeetCode Hot 100：128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：‌

输入：‌nums = $100,4,200,1,3,2$
输出：‌4
解释：‌最长数字连续序列是 $1, 2, 3, 4$ 。它的长度为 4。

示例 2：‌

输入：‌nums = $0,3,7,2,5,8,4,6,0,1$
输出：‌9

示例 3：‌

输入：‌nums = $1,0,1,2$
输出：‌3

提示：‌

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

题解

Go：

func longestConsecutive(nums []int) int {
    var hashTable = make(map[int]bool, len(nums))
    maxlength, length := 0, 0
    for _, num := range nums {
        hashTable[num] = true
    }
    for num, _ := range hashTable {
        length = 1
        if _, exists := hashTable[num - 1]; exists {
            continue
        }
        for hashTable[num + 1] {
            length ++
            num ++
        }
        if length > maxlength {
            maxlength = length
        }
    }
    return maxlength
}

Go 中没有单独的 set 集合，只有通过 map 来实现；可以使用map[int]struct{}，空结构体比 bool 更加节省空间和时间。

但使用空结构体就不能用for hashTable[num + 1] {这么省事的形式了，必须 for 死循环，然后自己控制 break。

func longestConsecutive(nums []int) int {
    var hashTable = make(map[int]struct{}, len(nums))
    maxlength, length := 0, 0
    for _, num := range nums {
        hashTable[num] = struct{}{}
    }
    for num, _ := range hashTable {
        length = 1
        if _, exists := hashTable[num - 1]; exists {
            continue
        }
        for {
            if _, exists := hashTable[num + 1]; exists {
                length ++
                num ++
            } else {
                break
            }
        }
        if length > maxlength {
            maxlength = length
        }
    }
    return maxlength
}

~~但是运行效率确实是实打实地提升了不少~~ 看错了，至少在 LeetCode 提供的数据量下提升约等于没有🤣

不得不感慨 Go 团队对于编译器和运行时的打磨真不是吾等小辈能想象的。

Java：

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        int maxlength = 0, length = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int num : set) {
            length = 1;
            if (set.contains(num - 1)) {
                continue;
            }
            while (set.contains(num + 1)) {
                length ++;
                num ++;
            }
            if (length > maxlength) {
                maxlength = length;
            }
        }
        return maxlength;
    }
}

Java 中有单独的 HashSet，注意其添加方式为add()而非put()。

记录

因为 Java 的 HashSet 底层其实就是基于 HashMap 实现的（它只是把 Set 的元素当作 Map 的 Key，而 Value 统一放一个无意义的虚无对象），所以它们的删除和包含 API 非常神似：

操作意图	`Set` 接口 (如 `HashSet`‌)‌	`Map` 接口 (如 `HashMap`‌)‌
添加/写入	`set.add(key)`	`map.put(key, value)`
删除/移除	`set.remove(key)`	`map.remove(key)`
检查是否存在	`set.contains(key)`	`map.containsKey(key)`

在 Go 语言中，不管是删除 map 的键值对，还是模拟 set 的删除，‌全都只有唯一的一个内置全局函数‌：delete(map, key)。
map 和 set 都能起到去重作用。当需要基于给定数据进行迭代时，注意是根据集合内容进行迭代还是根据未去重的原始内容进行迭代。