哈希表常见算法题——优化双循环、按键聚合、滑动窗口应用

1. 两数之和

题目(原题见LeetCode):

1
2
3
4
5
6
7
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

在该例子中,如果仅仅只是想在有解决方法时返回true时,我们可以使用哈希集合来存储迭代数组时所有值,并检查target - curret_value是否在哈希集合中。

但是如果我们被要求获取更多信息(如本题中需要返回索引值)。那么我们可以使用哈希映射来存储元素对应的索引值。

除此之外,本题还需要掌握的技巧是,可以通过哈希表还替代双循环。本题最简单的方法是可以通过暴力破解法穷举出可行的元素:

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}

采用暴力破解法时间的复杂度较高,但是并不是最优解。我们可以用哈希表来维护数组中每个元素与其索引相互对应的关系,采用更加高效的检查数组中是否存在目标元素的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
/* 遍历数组,将元素作为键,索引作为值存入到哈希表中 */
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i]; // 符合的元素
if (map.containsKey(complement) && map.get(complement) != i) {
/* 通过哈希表获取到符合元素的下标 */
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}

更为优化和简明的方法是:在进行迭代并将元素插入到表的同时,检查表中是否已经存在当前元素所对应的目标元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}
throw new IllegalArgumentException("No two sum solution");
}

2. 字符串中的第一个唯一字符

题目(原题见LeetCode):

1
2
3
4
5
6
7
8
9
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
案例:

s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.

注意事项:您可以假定该字符串只包含小写字母。

该题需要我们掌握的解决技巧是:按键聚合所有信息,即这对类似这题的“重复”问题,我们可以用哈希表来维护元素和出现次数的映射关系,计算出每个字符的出现次数,然后通过哈希表找出符合题意的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int firstUniqChar(String s) {
char[] chars = s.toCharArray();
HashMap<Character, Integer> hashMap = new HashMap<>();

/* 通过HashMap用来存储每个字符在单词中出现的次数 */
for (char ch : chars) {
int value = hashMap.getOrDefault(ch, 0) + 1;
hashMap.put(ch, value);
}
/* 遍历字符数组,查询该字符在字符串中出现的次数 */
for (int i = 0; i < chars.length; i++) {
if (hashMap.get(chars[i]) == 1) { // 出现唯一的字符
return i;
}
}
return -1;
}

该题还有一个时间复杂度较低的解决方法,通过枚举出a ~ z字符,然后通过indexOflastIndexOf相等的条件,找到字符串中唯一的字符:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int firstUniqChar(String s) {
if (s == null || s.length() == 0) return -1;

int res = Integer.MAX_VALUE;
for (char i = 'a'; i <= 'z'; i++) {
int index = s.indexOf(i);
/* 代表字符串中该字符第一次出现的索引和最后一个出现的索引一致,代表该字符串中
只有一个该字符 */
if (index != -1 && index == s.lastIndexOf(i)) {
res = Math.min(res, index); // 找到第一个符合条件的元素
}
}
return res;
}

3. 无重复字符的最长子串

题目(原题见LeetCode):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

该题掌握的技巧是:通过HashSet作为滑动窗口,来完成对字符是否在当前子字符串中的检查:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();

int res = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
/* 当不再哈希集合中时,继续滑动j */
set.add(s.charAt(j));
j++;
/* j - i即在此之前的无重复的最长子串,并将与res的最大值重新复制给res */
res = Math.max(res, j - i);
} else {
set.remove(s.charAt(i));
i++;
}
}
// 此时,我们找到的没有重复字符的最长字符串将会以索引i开头
return res;
}

下面是一段对窗口的解释,有助于更加了解滑动窗口的工作原理:

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j) 向右滑动 11 个元素,则它将变为 [i+1, j+1)(左闭,右开)。

—— 摘自LeetCode

Pushy wechat
欢迎订阅我的微信公众号