LeetCode每日三题（一）哈希
一、两数之和
自己答案：
class Solution {
public int[] twoSum(int[] nums, int target) {
//遍历每一个元素 如果满足条件则终止循环返回答案
int[] result=new int[2];
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if((nums[i]+nums[j])==target){
result[0]=i;
result[1]=j;
break;
}
}
}
return result;
}
}标准答案：
class Solution {
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])) {
//对于遍历到的元素，如果集合中存在另一个元素
//使得两者之和等于target
//返回该元素索引 以及 另一个元素对应的数组的索引 的数组
return new int[]{hashtable.get(target - nums[i]), i};
}
//如果不存在另一个元素，将这个元素值作为键 索引作为值 存入集合中
hashtable.put(nums[i], i);
}
return new int[0];
}
}二、字母异位词分组
自己答案：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,List<String>> map=new HashMap<>();
for(int i=0;i<strs.length;i++){
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
chars.toString();
//判断是否存在于map集合中
String Key=new String(chars);
if(map.containsKey(Key)){
//存在 则添加进map集合对应的值（集合）中
map.get(Key).add(strs[i]);
}else{
//不存在，新建一个对应键值
map.put(Key,new ArrayList<String>());
map.get(Key).add(strs[i]);
}
}
//利用多态来创建一个符合题目要求返回值类型的集合
ArrayList<List<String>> values =new ArrayList<List<String>>(map.values());
return values;
}
}标准答案：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}知识点：
①StringBuffer：
线程安全的可变字符序列。一个类似于 String 的字符串缓冲区，但不能修改。虽然在任意时间点上它都包含某种特定的字符序列，但通过某些方法调用可以改变该序列的长度和内容。
StringBuffer 上的主要操作是 append 和 insert 方法，可重载这些方法，以接受任意类型的数据。每个方法都能有效地将给定的数据转换成字符串，然后将该字符串的字符添加或插入到字符串缓冲区中。append 方法始终将这些字符添加到缓冲区的末端；而 insert 方法则在指定的点添加字符。
②map.getOrDefault：
map.getOrDefault 是 Java 中 Map 接口的一个方法，用于获取指定键的值。如果指定的键不存在于映射中，则返回一个默认值。 key: 要查找的键 defaultValue: 如果映射中不存在该键，则返回的默认值。
三、最长连续序列
自己答案：
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length!=0){//原数组进行排序
Arrays.sort(nums);
int[] arr = new int[]{nums[0], nums[0]};
int[] temparr = new int[]{nums[0], nums[0]};
int length = 1;
int temp = 1;
for (int i = 1; i < nums.length; i++) {
//遍历每个元素
if (((nums[i] - nums[i - 1]) == 1)||((nums[i] - nums[i - 1]) == 0)) {
//如果是呈连续
//记录当前值为end
temparr[1] = nums[i];
//记录临时连续长度
temp = temparr[1] - temparr[0] + 1;
} else {
//如果不连续
//比较已经记录下的连续长度
if (temp > length) {
//长度大于记录的最大长度
//更新数据
length = temp;
arr[0] = temparr[0];
arr[1] = temparr[1];
}
temparr[0] = nums[i];
temparr[1] = nums[i];
}
}
if (temp > length) {
//长度大于记录的最大长度
//更新数据
length = temp;
arr[0] = temparr[0];
arr[1] = temparr[1];
}
return length;
}else return 0;
}
}没有满足时间复杂度为 O(n)
标准答案：
class Solution {
public int longestConsecutive(int[] nums) {
//创建Set集合
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int result = 0;
for (Integer num : set) {
if(!(set.contains(num-1))){
int currentlength=1;
while((set.contains(num+1))){
num+=1;
currentlength++;
}
result=Math.max(result,currentlength);
}
}
return result;
}
}