Hot100之哈希

1两数之和

题目

思路解析

解法1--两次循环

解法2--哈希表一次循环

代码

解法1--两次循环

class Solution {public int[] twoSum(int[] nums, int target) {int nums1[] = new int[2];int length = nums.length;for (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {if (nums[i] + nums[j] == target) {nums1[0] = i;nums1[1] = j;return nums1;}}}return nums1;}
}

解法2--哈希表一次循环

import java.util.HashMap;
import java.util.Map;class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);}return new int[]{};}
}

---

49字母异位词分组 

题目

思路解析

我们利用一个Map结构Map<String,List>

然后我们把字符串String变成我们的char【】数组，然后Arrays.sort（）对字符数组进行排序

将排序后的字符数组变成String放到Map中（这样子就能保证ate，eat，tea的value就是排序后的字符数组aet）

最后通过return new ArrayList(map.values())，将Map中的所有键值对构造成List

代码

class Solution {public List<List<String>> groupAnagrams(String[] strs) {if (strs.length == 0 || strs == null) {return new ArrayList();}Map<String, List> map = new HashMap<String, List>();for (String s : strs) {// 将字符串转化为字符数组char[] chars = s.toCharArray();// 对字符数组按照字母顺序排序Arrays.sort(chars);// 将排序后的字符串作为哈希表中的key值String key = String.valueOf(chars);// 判断哈希表中是否有该key值if (!map.containsKey(key)) {// 若不存在，则为新的异位词语，在map中创建新的键值对map.put(key, new ArrayList());}// 将该字符串放在对应key的list中map.get(key).add(s);}// 返回map中所有键值对象构成的listreturn new ArrayList(map.values());}
}

 

---

128最长连续数列

题目

思路解析

我们通过Set结构的contains()来看看是否有连续的变量

我们开始计算的条件是：我们该元素-1不存在，说明这就是连续递增元素的头，我们从这个开始计算

如果我们前面元素存在，说明这个元素不是连续递增元素的头，我们要求最长连续数列，所以没必要计算

        for (int num : set) {// 说明不会重复,因为1,2,3,4我们已经算完了,我们还从2,3,4算起就没必要了// 因为我的最长已经从第一个最小数字开始算出来了//所以我们在元素x的时候，如果我们的元素x-1不存在，说明前面没有连续的，我们在x开始遍历//如果我们的元素x-1存在，说明它不是连续递增的头，所以没必要遍历if (!set.contains(num - 1)) {int currentNum = num; // 一个变量用来++int currentMax = 1;while (set.contains(currentNum + 1)) {currentNum++;currentMax++;}maxlength = Math.max(maxlength, currentMax);}}

代码

class Solution {public int longestConsecutive(int[] nums) {// 利用Set结构,把数字都放到Set结构里面Set<Integer> set = new HashSet<Integer>();for (int num : nums) {set.add(num);}int maxlength = 0;for (int num : set) {// 说明不会重复,因为1,2,3,4我们已经算完了,我们还从2,3,4算起就没必要了// 因为我的最长已经从第一个最小数字开始算出来了//所以我们在元素x的时候，如果我们的元素x-1不存在，说明前面没有连续的，我们在x开始遍历//如果我们的元素x-1存在，说明它不是连续递增的头，所以没必要遍历if (!set.contains(num - 1)) {int currentNum = num; // 一个变量用来++int currentMax = 1;while (set.contains(currentNum + 1)) {currentNum++;currentMax++;}maxlength = Math.max(maxlength, currentMax);}}return maxlength;}
}