hashtable
概念
哈希表是使用哈希的技术提供从键到值的映射的数据结构，我们将其称为键值对，键必须是唯一的，但值可以重复
哈希表中可以放置的键值对可以是任意类型，不仅仅是字符串和数字，还可以是对象！但是，键需要是可哈希的，
使用场景：判断一个元素是否出现集合里，出现次数
哈希函数 H(x) 是将键“x”映射到固定范围内的整数的函数。可以为任意对象（例如字符串、列表、元组、多数据对象等）定义哈希函数。
哈希冲突：如果 H(x)=H(y)，则对象 x 和 y可能相等，但如果 H(x)≠ H(y)，则 x 和 y 肯定不相等。与其直接比较 x 和 y，更聪明的方法是先比较它们的哈希值，只有当哈希值匹配时，我们才需要明确比较 x 和
例如比较2个大文件的内容是否相等，可以用文件的哈希函数比较，避免打开文件。文件的哈希函数比哈希表使用的哈希函数更复杂，对于文件，我们使用所谓的加密哈希函数，也称为校验和。哈希函数 H(x) 必须是确定性的。如果 H(x)=y，则 H(x) 必须始终产生 y，而不会产生其他值。
解决hash冲突的方法:链地址法通过维护一个数据结构（通常是链接列表）来保存散列到特定值的所有不同值，从而解决散列冲突问题。
注意：用于缓存散列到特定值的项目的数据结构不限于链接列表，一些实现使用以下一种或多种混合：数组、二叉树、自平衡树等。HT数据太多，如何保持 o(1) 插入和查找时间复杂度？创建一个具有更大容量的新 HT，并重新散列旧 HT 内的所有项目，并将它们分散到新 HT 的不同位置。
算法复杂度
Operation Average Worst
Insertion 0(1)* o(n)
Removal 0(1)* o(n)
Search 0(1)* o(n)
链地址法代码实现
/**
* An implementation of a hash-table using separate chaining with a linked list.
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.datastructures.hashtable;
import java.util.*;
class Entry<K, V> {
int hash;
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
this.hash = key.hashCode();
}
// We are not overriding the Object equals method
// No casting is required with this method.
public boolean equals(Entry<K, V> other) {
if (hash != other.hash) return false;
return key.equals(other.key);
}
@Override
public String toString() {
return key + " => " + value;
}
}
@SuppressWarnings("unchecked")
public class HashTableSeparateChaining<K, V> implements Iterable<K> {
private static final int DEFAULT_CAPACITY = 3;
private static final double DEFAULT_LOAD_FACTOR = 0.75;
private double maxLoadFactor;
private int capacity, threshold, size = 0;
private LinkedList<Entry<K, V>>[] table;
public HashTableSeparateChaining() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashTableSeparateChaining(int capacity) {
this(capacity, DEFAULT_LOAD_FACTOR);
}
// Designated constructor
public HashTableSeparateChaining(int capacity, double maxLoadFactor) {
if (capacity < 0) throw new IllegalArgumentException("Illegal capacity");
if (maxLoadFactor <= 0 || Double.isNaN(maxLoadFactor) || Double.isInfinite(maxLoadFactor))
throw new IllegalArgumentException("Illegal maxLoadFactor");
this.maxLoadFactor = maxLoadFactor;
this.capacity = Math.max(DEFAULT_CAPACITY, capacity);
threshold = (int) (this.capacity * maxLoadFactor);
table = new LinkedList[this.capacity];
}
// Returns the number of elements currently inside the hash-table
public int size() {
return size;
}
// Returns true/false depending on whether the hash-table is empty
public boolean isEmpty() {
return size == 0;
}
// Converts a hash value to an index. Essentially, this strips the
// negative sign and places the hash value in the domain [0, capacity)
private int normalizeIndex(int keyHash) {
return (keyHash & 0x7FFFFFFF) % capacity;
}
// Clears all the contents of the hash-table
public void clear() {
Arrays.fill(table, null);
size = 0;
}
public boolean containsKey(K key) {
return hasKey(key);
}
// Returns true/false depending on whether a key is in the hash table
public boolean hasKey(K key) {
int bucketIndex = normalizeIndex(key.hashCode());
return bucketSeekEntry(bucketIndex, key) != null;
}
// Insert, put and add all place a value in the hash-table
public V put(K key, V value) {
return insert(key, value);
}
public V add(K key, V value) {
return insert(key, value);
}
public V insert(K key, V value) {
if (key == null) throw new IllegalArgumentException("Null key");
Entry<K, V> newEntry = new Entry<>(key, value);
int bucketIndex = normalizeIndex(newEntry.hash);
return bucketInsertEntry(bucketIndex, newEntry);
}
// Gets a key's values from the map and returns the value.
// NOTE: returns null if the value is null AND also returns
// null if the key does not exists, so watch out..
public V get(K key) {
if (key == null) return null;
int bucketIndex = normalizeIndex(key.hashCode());
Entry<K, V> entry = bucketSeekEntry(bucketIndex, key);
if (entry != null) return entry.value;
return null;
}
// Removes a key from the map and returns the value.
// NOTE: returns null if the value is null AND also returns
// null if the key does not exists.
public V remove(K key) {
if (key == null) return null;
int bucketIndex = normalizeIndex(key.hashCode());
return bucketRemoveEntry(bucketIndex, key);
}
// Removes an entry from a given bucket if it exists
private V bucketRemoveEntry(int bucketIndex, K key) {
Entry<K, V> entry = bucketSeekEntry(bucketIndex, key);
if (entry != null) {
LinkedList<Entry<K, V>> links = table[bucketIndex];
links.remove(entry);
--size;
return entry.value;
} else return null;
}
// Inserts an entry in a given bucket only if the entry does not already
// exist in the given bucket, but if it does then update the entry value
private V bucketInsertEntry(int bucketIndex, Entry<K, V> entry) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
if (bucket == null) table[bucketIndex] = bucket = new LinkedList<>();
Entry<K, V> existentEntry = bucketSeekEntry(bucketIndex, entry.key);
if (existentEntry == null) {
bucket.add(entry);
if (++size > threshold) resizeTable();
return null; // Use null to indicate that there was no previous entry
} else {
V oldVal = existentEntry.value;
existentEntry.value = entry.value;
return oldVal;
}
}
// Finds and returns a particular entry in a given bucket if it exists, returns null otherwise
private Entry<K, V> bucketSeekEntry(int bucketIndex, K key) {
if (key == null) return null;
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
if (bucket == null) return null;
for (Entry<K, V> entry : bucket) if (entry.key.equals(key)) return entry;
return null;
}
// Resizes the internal table holding buckets of entries
private void resizeTable() {
capacity *= 2;
threshold = (int) (capacity * maxLoadFactor);
LinkedList<Entry<K, V>>[] newTable = new LinkedList[capacity];
for (int i = 0; i < table.length; i++) {
if (table[i] != null) {
for (Entry<K, V> entry : table[i]) {
int bucketIndex = normalizeIndex(entry.hash);
LinkedList<Entry<K, V>> bucket = newTable[bucketIndex];
if (bucket == null) newTable[bucketIndex] = bucket = new LinkedList<>();
bucket.add(entry);
}
// Avoid memory leak. Help the GC
table[i].clear();
table[i] = null;
}
}
table = newTable;
}
// Returns the list of keys found within the hash table
public List<K> keys() {
List<K> keys = new ArrayList<>(size());
for (LinkedList<Entry<K, V>> bucket : table)
if (bucket != null) for (Entry<K, V> entry : bucket) keys.add(entry.key);
return keys;
}
// Returns the list of values found within the hash table
public List<V> values() {
List<V> values = new ArrayList<>(size());
for (LinkedList<Entry<K, V>> bucket : table)
if (bucket != null) for (Entry<K, V> entry : bucket) values.add(entry.value);
return values;
}
// Return an iterator to iterate over all the keys in this map
@Override
public java.util.Iterator<K> iterator() {
final int elementCount = size();
return new java.util.Iterator<K>() {
int bucketIndex = 0;
java.util.Iterator<Entry<K, V>> bucketIter = (table[0] == null) ? null : table[0].iterator();
@Override
public boolean hasNext() {
// An item was added or removed while iterating
if (elementCount != size) throw new java.util.ConcurrentModificationException();
// No iterator or the current iterator is empty
if (bucketIter == null || !bucketIter.hasNext()) {
// Search next buckets until a valid iterator is found
while (++bucketIndex < capacity) {
if (table[bucketIndex] != null) {
// Make sure this iterator actually has elements -_-
java.util.Iterator<Entry<K, V>> nextIter = table[bucketIndex].iterator();
if (nextIter.hasNext()) {
bucketIter = nextIter;
break;
}
}
}
}
return bucketIndex < capacity;
}
@Override
public K next() {
return bucketIter.next().key;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// Returns a string representation of this hash table
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < capacity; i++) {
if (table[i] == null) continue;
for (Entry<K, V> entry : table[i]) sb.append(entry + ", ");
}
sb.append("}");
return sb.toString();
}
}
开放地址法代码实现
哈希表 (HT) 的目标是构建从键到值的映射
键必须是可哈希的，我们需要一个将键转换为整数的哈希函数。
我们使用在键集上定义的哈希函数来索引数组（哈希表）
哈希函数并不完美，因此有时两个键 k、k2（k1 ≠ k2）哈希为相同的值。当发生这种情况时，我们就会遇到哈希冲突（即 H(k1)= H(k2)）
开放寻址是解决此问题的一种方法
当使用开放寻址作为冲突解决技术时，键值对存储在表（数组）本身中，而不是像单独链接中的数据结构
这意味着我们需要非常关注哈希表的大小以及表中当前有多少元素。
加载因子 =表中的项目/表的大小
当我们想要将一个键值对 (k,v) 插入到哈希表中时，我们会对键进行哈希处理，并获得此键值对所属的原始位置，即 H(k)。
如果键哈希到的位置已被占用，我们会通过根据探测序列 P(x) 偏移当前位置来尝试哈希表中的另一个位置，我们一直这样做，直到找到一个未占用的位置。
你可以想出无数个探测序列，这里列举几个：
线性探测：P(x)= ax + b，其中 a、b 为常数
二次探测：P(x)= ax2 + bx+c，其中 a、b、c 为常数
双重哈希：P(k,x)=xHz(k)，其中 Hz(k) 是二次哈希函数
伪随机数生成器：P(k,x)=xRNG(H(k),x)，其中 RNG 是以 H(k) 为种子的随机数生成器函数
大多数随机选择的模 N 探测序列将产生比表大小更短的循环。当您尝试插入键值对并且循环上的所有存储桶都被占用时，这会出现问题，因为您将陷入无限循环！
问：如何处理产生比表大小更短的循环的探测函数？
答：一般来说，共识是我们不处理这个问题，而是通过将探测函数的范围限制为产生正好长度为 N 的循环的函数来完全避免它*
*有一些具有特殊属性的例外,可以产生更短的循环。
线性探测、二次探测和双重哈希等技术都存在导致循环的问题，这就是为什么这些方法使用的探测函数是特定的，
请注意，开放寻址对所使用的哈希函数和探测函数非常敏感：如果您使用分离链接作为冲突解决方法，您不必（过多）担心这一点
问：P(x)=ax 中常数 a负载因子 的哪些值会产生模 N 总数的完整循环？
答：当 a 和 N 互质时，即两个数字的最大公约数 (GcD) 等于一。因此，当 Gcp(a,N)= 1 时，探测函数 P(x) 能够生成一个完整循环，并且我们总能找到一个空桶！因此选择互为质数的数字作为模避免死循环，或者P(x) 的一个常见选择是 P(x)= 1X因为 GcD(N,1)=1，无论 N(表大小) 的选择如何
Probing function:P(x)=5X
Fixed table size:N=12
Max load factor:a=0.35
Threshold before resize=N*=4
OP 是一种探测方法，它根据二次公式进行探测，具体来说：
P(x)= ax2 + bx +c，其中 a、b、c 为常数，且 a ≠（否则我们进行线性探测）（注意：常数 c 已过时，您知道为什么吗？）
但是，正如我们之前所看到的，并非所有二次函数都是可行的，因为它们无法产生 N 阶循环。我们需要某种方法来处理这个问题。
问：那么我们如何选择一个可以使用的探测函数？
答：有很多方法，但最流行的三种方法是：
1）让 P(x)=x2，保持表大小为素数>3，并保持a小于等于二分之一
2）让 P(x)=(x^2 + x)/2，保持表大小为 2 的幂
3）让 P(x)=(-1^x)*x2，保持表大小为素数 N，其中 N≡3 mod 4
双重hash DH 是一种根据另一个哈希函数的常数倍数进行探测的探测方法，具体为：
P(k,x)= x*H(k)，其中 H(k) 是
第二个哈希函数
Hz(k) 必须散列与 H(k) 相同类型的key.比如都是字符串
注意：请注意，加倍散列会减少为线性探测（除了常数直到运行时才知道）
避免死循环，首先哈希表的大小必须是质数，然后令δ=H2(k)mod N 当δ=0就会死循环，我们需要强制设置为δ=1
通常，选择用于组成 Hz(k) 的哈希函数是从称为通用哈希函数的哈希函数池中挑选出来的，这些哈希函数通常对一种基本数据类型进行操作。
开放地址删除连续的线性探测中间数据时，将该数据设置为“墓碑”，查询时跳过墓碑，避免找不到数据
0：我的 HT 中有很多墓碑，我该如何清除它们？
答：墓碑在 HT 中算作已填充的槽位，因此它们会增加负载因子，并在调整表大小时被移除。此外，插入新的 (k,v) 对时，您可以用新的键值对替换带有墓碑的存储桶
/**
* An implementation of a hash-table using open addressing with quadratic probing as a collision
* resolution method.
*
* <p>In this implementation we are using the following probing function: H(k, x) = h(k) + f(x) mod
* 2^n
*
* <p>Where h(k) is the hash for the given key, f(x) = (x + x^2) / 2 and n is a natural number. We
* are using this probing function because it is guaranteed to find an empty cell (i.e it generates
* all the numbers in the range [0, 2^n) without repetition for the first 2^n numbers).
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.datastructures.hashtable;
@SuppressWarnings("unchecked")
public class HashTableQuadraticProbing<K, V> extends HashTableOpenAddressingBase<K, V> {
public HashTableQuadraticProbing() {
super();
}
public HashTableQuadraticProbing(int capacity) {
super(capacity);
}
// Designated constructor
public HashTableQuadraticProbing(int capacity, double loadFactor) {
super(capacity, loadFactor);
}
// Given a number this method finds the next
// power of two above this value.
private static int nextPowerOfTwo(int n) {
return Integer.highestOneBit(n) << 1;
}
// No setup required for quadratic probing.
@Override
protected void setupProbing(K key) {}
@Override
protected int probe(int x) {
// Quadratic probing function (x^2+x)/2
return (x * x + x) >> 1;
}
// Increase the capacity of the hashtable to the next power of two.
@Override
protected void increaseCapacity() {
capacity = nextPowerOfTwo(capacity);
}
// Adjust the capacity of the hashtable to be a power of two.
@Override
protected void adjustCapacity() {
int pow2 = Integer.highestOneBit(capacity);
if (capacity == pow2) return;
increaseCapacity();
}
}
242有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
时间复杂度O(m+n)
空间复杂度O(1)
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
record[t.charAt(i) - 'a']--;
}
for (int count: record) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
if (count != 0) {
return false;
}
}
return true;// record数组所有元素都为零0，说明字符串s和t是字母异位词
}
}
383赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// shortcut
if (ransomNote.length() > magazine.length()) {
return false;
}
// 定义一个哈希映射数组
int[] record = new int[26];
// 遍历
for(char c : magazine.toCharArray()){
record[c - 'a'] += 1;
}
for(char c : ransomNote.toCharArray()){
record[c - 'a'] -= 1;
}
// 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
for(int i : record){
if(i < 0){
return false;
}
}
return true;
}
}
349两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
//遍历数组1
for (int i : nums1) {
set1.add(i);
}
//遍历数组2的过程中判断哈希表中是否存在该元素
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
//方法1：将结果集合转为数组
return resSet.stream().mapToInt(x -> x).toArray();
//方法2：另外申请一个数组存放setRes中的元素,最后返回数组
int[] arr = new int[resSet.size()];
int j = 0;
for(int i : resSet){
arr[j++] = i;
}
return arr;
}
}
202快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：输入：19 输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (n != 1 && !record.contains(n)) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
454四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如: 输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:2
解释:两个元组如下:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}
t1两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
示例 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
t49字母异位词分组
- 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
- 示例 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]，输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
时间复杂度O(nklogk)，n、k是strs中的字符串的数量和最大长度。需要遍历n个字符串，
对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，总时间复杂度O(nklogk)
空间复杂度O(nk)，n 、k是strs 中的字符串的数量和最大长度。需要用哈希表存储全部字符串
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> hashMap = new HashMap<String,List<String>>();
for(String s: strs){
char[] split = s.toCharArray();
Arrays.sort(split);
String newStr = new String(split);
List<String> list = hashMap.getOrDefault(newStr,new ArrayList<String>());
list.add(s);
hashMap.put(newStr,list);
}
return new ArrayList<List<String>>(hashMap.values());
}
}
t128最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：输入：nums = [100,4,200,1,3,2] 输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
时间复杂度：O(n)，其中 n 为数组的长度。具体分析已在上面正文中给出。
空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n) 的空间。
class Solution {
public int longestConsecutive(int[] nums) {
//去重
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;//如果集合中不包含 num - 1，意味着 num 是某个连续序列的起点。
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
//每次都更新序列的最大值
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
public int longestConsecutive(int[] nums) {
// key表示num，value表示num所在连续区间的长度
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for (int num : nums) {
// 当map中不包含num，也就是num第一次出现
if (!map.containsKey(num)) {
// left为num-1所在连续区间的长度，更进一步理解为：左连续区间的长度
int left = map.getOrDefault(num - 1, 0);
// right为num+1所在连续区间的长度，更进一步理解为：右连续区间的长度
int right = map.getOrDefault(num + 1, 0);
// 当前连续区间的总长度
int curLen = left + right + 1;
ans = Math.max(ans, curLen);
// 将num加入map中，表示已经遍历过该值。其对应的value可以为任意值。
map.put(num, -1);
// 更新当前连续区间左边界和右边界对应的区间长度
map.put(num - left, curLen);
map.put(num + right, curLen);
}
}
return ans;
}