leetcode刷题记录——哈希表
2024-08-27 23:06:41
1.两数之和
可以先对数组进行排序，然后使用双指针方法或者二分查找方法。这样做的时间复杂度为 O(NlogN)，空间复杂度为 O(1)。
用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]，如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> indexForNum = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (indexForNum.containsKey(target - nums[i])) {
return new int[]{indexForNum.get(target - nums[i]), i};
} else {
indexForNum.put(nums[i], i);
}
}
return null;
}
}
217.存在重复元素
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
return set.size() < nums.length;
}
}
594.最长和谐子序列
和谐序列中最大数和最小数之差正好为 1，应该注意的是序列的元素不一定是数组的连续元素。
class Solution {
public int findLHS(int[] nums) {
Map<Integer, Integer> countForNum = new HashMap<>();
for (int num : nums) {
countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
}
int longest = 0;
for (int num : countForNum.keySet()) {
if (countForNum.containsKey(num + 1)) {
longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
}
}
return longest;
}
}
128.最长连续序列
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;
int currentStreak = 1;
while (num_set.contains(currentNum+1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
最新文章
- mahout 安装测试
- 自定义ViewGroup
- IOS - delegate为什么不使用retain
- HDU-1231 简单dp，连续子序列最大和，水
- unity3d c#脚本定义Transform
- NV 200, 300, 400, 500, 600, 700, 800
- JDBC学习笔记(1)——JDBC概述
- （转）Memcached
- KVC vs KVO(内容为转载记录,整合大家的总结为我所用)
- A Tour of Go If with a short statement
- virtualbox 安装windows系统的一些问题
- Yii2设计模式——静态工厂模式
- python———day03
- IOS 静态库 和 动态库
- PDF文件如何标注，怎么使用PDF标注工具
- No write since last change (add ! to override)
- [SoapUI] 从上一个测试步骤获取ID list，通过Groovy脚本动态生成 Data Source 供后面的步骤使用
- SpringMvc4中获取request、response对象的方法
- CodeForces - 768C Jon Snow and his Favourite Number 桶排
- 转: 用 Go 写一个轻量级的 ldap 测试工具