SYSTEM
哈希
src/content/notes/system/哈希.md 1.5 哈希
两数之和(力扣 1)
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(); // 值 -> 下标
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
最长连续序列(力扣 128)
把数放进集合,只从”序列起点”(num-1 不在集合中)开始向上数,避免重复枚举,整体 O(N)。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);
int max = 0;
for (int n : set) {
if (set.contains(n - 1)) continue; // 不是起点,跳过
int cur = n, len = 1;
while (set.contains(cur + 1)) { cur++; len++; }
max = Math.max(max, len);
}
return max;
}
}