Leetcode Hot 100
哈希
两数之和
链接：1. 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
1
2
3
| 输入：nums = , target = 9
输出：
解释：因为 nums + nums == 9 ，返回 。
|
示例 2：
1
2
| 输入：nums = , target = 6
输出：
|
示例 3：
1
2
| 输入：nums = , target = 6
输出：
|
提示：
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
题解
我的题解
首先将数据全部存入哈希表中，哈希表的key是nums，value是一个数组ArrayList，存储相同的nums所在的位置，因为同一个数组可能存在于不同的位置。
在查找target的时候，首先遍历哈希表，每次拿到一个数k，通过get方法查找target-k，如果存在则查到到正确结果。因为有可能是相同的两个数加起来为target，所以需要拿到ArrayList的两个不同的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
ArrayList<Integer> arrayList = map.get(nums[i]);
if(arrayList == null){
arrayList = new ArrayList<>();
}
arrayList.add(i);
map.put(nums[i], arrayList);
}
int[] results = new int[2];
Set<Integer> mykey = map.keySet();
for (Integer k : mykey) {
if(map.get(target - k) != null){
results[0] = map.get(k).get(0);
if(target - k == k){
results[1] = map.get(k).get(1);
}else{
results[1] = map.get(target-k).get(0);
}
return results;
}
}
return results;
}
}
|
官方题解
使用哈希表，可以将寻找target - x的时间复杂度降低到从O(N)降低到O(1)。
创建一个哈希表，对于每一个x，首先查询哈希表中是否存在target - x，然后将x插入到哈希表中，即可保证不会让x和自己匹配。
复杂度分析
时间复杂度：O(N)，其中N是数组中的元素数量。对于每一个元素x，可以O(1)地寻找target - x。
空间复杂度：O(N)，其中N是数组中的元素数量。主要为哈希表的开销。
1
2
3
4
5
6
7
8
9
10
11
12
| 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 null;
}
}
|
字母异位词分组
链接：49. 字母异位词分组
题目
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
1
2
| 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
|
示例 2:
1
2
| 输入: strs = [""]
输出: [[""]]
|
示例 3:
1
2
| 输入: strs = ["a"]
输出: [["a"]]
|
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] 仅包含小写字母
数据输入：
1
2
3
4
5
6
7
8
| public static void main(String[] args) {
String [] list = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> results = new ArrayList<>();
results = groupAnagrams(list);
System.out.println(results);
}
|
题解
我的题解
因为字母异味词的字母成分是相同的，可以重载哈希表的equals和hashCode方法，让字母异味词的key值的equals和hashCode返回结果相同，从而put的时候找到相同的位置，value值是一个数组，存储字母异味词的数组下标。
参考链接：
1.哈希表的存储原理。
彻底搞懂equals以及hashCode方法（源码级分析）_equalsandhashcode-CSDN博客
2.String重写hashCode和equals方法。
String重写hashCode和equals方法_string重写了hashcode吗-CSDN博客
一文说透String的hashCode_string hashcode-CSDN博客
3.Java将字符串中字符按从小到大排序。
java将字符串中字符按从小到大排序_mob64ca12e6b22d的技术博客_51CTO博客
4.Java初始化List。
Java 中初始化 List 集合的 8 种方式!_java list初始化赋值-CSDN博客
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
static List<List<String>> groupAnagrams(String[] strs) {
Map<MyString, List<Integer>> map = new HashMap<>();
for (int i=0; i<strs.length; i++) {
MyString m = new MyString(strs[i]);
if(map.get(m) != null) {
map.get(m).add(i);
}else {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(m, list);
}
}
List<List<String>> result = new ArrayList<>();
map.forEach((k, v) -> {
List<String> list = new ArrayList<>();
List<Integer> indexs = map.get(k);
for (int i=0; i<indexs.size(); i++) {
list.add(strs[indexs.get(i)]);
}
result.add(list);
});
return result;
}
static class MyString{
String name;
public MyString(String name) {this.name = name;}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MyString oString = (MyString) o;
char [] thisName = name.toCharArray();
char [] oName = oString.name.toCharArray();
Arrays.sort(thisName);
Arrays.sort(oName);
return Arrays.equals(thisName, oName);
}
@Override
public int hashCode() {
char [] thisName = name.toCharArray();
Arrays.sort(thisName);
String value = Arrays.toString(thisName);
int h = value.hashCode();
return h;
}
}
}
|
官方题解
两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。
遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。
以下的两种方法分别使用排序和计数作为哈希表的键。
方法一：排序
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
复杂度分析
时间复杂度：O(nklogk)，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要遍历n个字符串，对于每个字符串，需要O(klogk)的时间进行排序以及O(1)的时间更新哈希表，因此总时间复杂度是O(nklogk)。
空间复杂度：O(nk)，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要用哈希表存储全部字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
|
方法二：计数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为26的数组记录每个字母出现的次数。
复杂度分析
时间复杂度：O(n(k+∣Σ∣))，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度，Σ是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要遍历n个字符串，对于每个字符串，需要O(k)的时间计算每个字母出现的次数，O(∣Σ∣)的时间生成哈希表的键，以及O(1)的时间更新哈希表，因此总时间复杂度是O(n(k+∣Σ∣))。
空间复杂度：O(n(k+∣Σ∣))，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度，Σ是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为O(∣Σ∣)，在渐进意义下小于O(n(k+∣Σ∣))，可以忽略不计。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| 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']++;
}
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());
}
|
最长连续序列
链接：128. 最长连续序列
题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
1
2
3
| 输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
|
示例 2：
1
2
| 输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
|
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
题解
我的题解
我的只对了72/76，有些样例时间超限了，时间复杂度太高了。（不一定正确）
思路：用并查集的思想。
首先用哈希表存储该数组，key和value值相同。
然后遍历哈希表，如果该数前面有相邻的数，将该数的value改为前一位数的value，代表他们属于同一个集合。如果该数后面有相邻的数，将后面数的value改为该数的value，也代表他们属于同一个集合。这样，该数和左边右边邻居都属于一个集合。
因为同一个集合的数的value都不一定相同，所以要将同一个集合的value统一。所以接着用并查集的思想遍历，将一个集合的所有value值统一。
最后统计value值最多的，即为最长的连续数字。
参考链接：
1.并查集
算法学习笔记(1) : 并查集 - 知乎
【算法与数据结构】—— 并查集-CSDN博客
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public int longestConsecutive(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], nums[i]);
}
for (int i = 0; i < nums.length; i++) {
if(map.get(nums[i] - 1) != null){
map.put(nums[i], map.get(nums[i] - 1));
}
if(map.get(nums[i] + 1) != null){
map.put(nums[i] + 1, map.get(nums[i]));
}
}
for (int i = 0; i < nums.length; i++) {
int k = nums[i];
int v = map.get(nums[i]);
while (k != v){
k = map.get(v);
v = map.get(k);
}
map.put(nums[i], k);
}
HashMap<Integer,Integer> map2 = new HashMap<>();
map.forEach((k,v) ->{
if(map2.get(v) == null){
map2.put(v,1);
}else {
map2.put(v,map2.get(v)+1);
}
});
Integer max = 0;
for (Map.Entry<Integer, Integer> entry : map2.entrySet()) {
if (entry.getValue() > max) {
max = entry.getValue();
}
}
return max;
}
}
|
官方题解
方法一：哈希表
我们考虑枚举数组中的每个数x，考虑以其为起点，不断尝试匹配x+1,x+2,⋯是否存在，假设最长匹配到了x+y，那么以x为起点的最长连续序列即为x,x+1,x+2,⋯,x+y，其长度为y+1，我们不断枚举并更新答案即可。
对于匹配的过程，暴力的方法是O(n)遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至O(1)的时间复杂度。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到O(n^2)（即外层需要枚举O(n)个数，内层需要暴力匹配O(n)次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个x,x+1,x+2,⋯,x+y的连续序列，而我们却重新从x+1，x+2或者是x+y处开始尝试匹配，那么得到的结果肯定不会优于枚举x为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数x一定是在数组中不存在前驱数x−1的，不然按照上面的分析我们会从x−1开始尝试匹配，因此我们每次在哈希表中检查是否存在x−1即能判断是否需要跳过了。
增加了判断跳过的逻辑之后，时间复杂度是多少呢？外层循环需要O(n)的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为O(n)，符合题目要求。
复杂度分析
时间复杂度：O(n)，其中n为数组的长度。具体分析已在上面正文中给出。
空间复杂度：O(n)。哈希表存储数组中所有的数需要O(n)的空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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;
}
}
|
方法二：哈希表记录右边界
这种方法其实也是方法一的变种，用于减少遍历次数。做法是建立一个哈希表，记录每个元素num能够连续到达的右边界，这样在内层循环遍历到一个新元素时，无需经过多次+1「遍历+判断」才能到达右边界，直接取值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, num);
}
int ans = 0;
for (int num : nums) {
if (!map.containsKey(num - 1)) {
int right = map.get(num);
while (map.containsKey(right + 1)) {
right = map.get(right + 1);
}
map.put(num, right);
ans = Math.max(ans, right - num + 1);
}
}
return ans;
}
}
|
方法三：哈希表记录连续区间长度（动态规划）
这是一种非常巧妙的做法，与方法二相同的一点是也利用了Map减小遍历次数。但很重要的一点不同是其value表示的是num所在的连续区间长度。举个例子，当Map的key为5，value为3时，这就表明当前有一个包含5且长度为3的连续区间，当然有多种可能，可以是[3,5],[4,6],[5,7]。
具体做法是：
遍历nums数组中的所有数字num，
当num是第一次出现时：
（1）分别获取到左相邻数字num-1的连续区间长度left和右相邻数字num+1的连续区间长度right；
（2）计算得到当前的区间长度为curLen=left+right+1；
（3）更新最长区间长度ans以及左右边界的区间长度。
在代码中的left和right能够分别代表num-1的左连续区间的长度和num+1的右连续区间长度，那么为什么map中的value能够时而表示左区间的长度，时而表示右区间的长度呢？
关键在于判断条件上：if (!map.containsKey(num))，这行代码表示num之前并未出现过。那么对于key=num-1来说，它的value表示的区间就只能是[num-value,num-1]，num-1只能是该区间的左边界值，而其它可能的连续区间都会包含num，不符合上述条件；同理，对于key=num+1来说，它的value表示的区间就只能是[num+1,num+value]，num+1`只能是该区间的右边界值。
当num已经出现了，这两个区间就可以被联通表示为[num-value1,num+value2]，当前连续区间的左右边界会发生变化，变为num-value1和num+value2，因此我们需要更新这两个边界点对应的区间长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for (int num : nums) {
if (!map.containsKey(num)) {
int left = map.getOrDefault(num - 1, 0);
int right = map.getOrDefault(num + 1, 0);
int curLen = left + right + 1;
ans = Math.max(ans, curLen);
map.put(num, -1);
map.put(num - left, curLen);
map.put(num + right, curLen);
}
}
return ans;
}
}
|
方法四：并查集
并查集的思路实际上与思路2有点像，也是来记录右边界的，所有在一个连续区间内的元素都会在一个连通分量中，且这些元素的根结点都为最远的右边界元素。
具体思路是：
遍历所有元素num，如果num+1存在，将num加入到num+1所在的连通分量中；
重新遍历一遍所有元素num，通过find函数找到num所在分量的根结点，也就是最远右边界，从而求得连续区间的长度。
加入了一个count哈希表，用于记录每个连通分量的节点个数，这样可在主函数一次遍历便可得到答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class UnionFind {
private Map<Integer, Integer> parent;
private Map<Integer, Integer> count;
public UnionFind(int[] nums) {
parent = new HashMap<>();
count = new HashMap<>();
for (int num : nums) {
parent.put(num, num);
count.put(num, 1);
}
}
public Integer find(int x) {
if (!parent.containsKey(x)) {
return null;
}
while (x != parent.get(x)) {
parent.put(x, parent.get(parent.get(x)));
x = parent.get(x);
}
return x;
}
public int union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return count.get(rootX);
}
parent.put(rootX, rootY);
count.put(rootY, count.get(rootX) + count.get(rootY));
return count.get(rootY);
}
}
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
UnionFind uf = new UnionFind(nums);
int ans = 1;
for (int num : nums) {
if (uf.find(num + 1) != null) {
ans = Math.max(ans, uf.union(num, num + 1));
}
}
return ans;
}
}
|