可信网站认证代理,从网络营销策划理论,最近热点新闻事件2023,北京网站制作排名哈希 1. 两数之和题目描述解题思路步骤#xff1a;时间复杂度#xff1a;空间复杂度#xff1a; 代码实现 2. 字母异位词分组题目描述解题思路步骤#xff1a;时间复杂度#xff1a;空间复杂度#xff1a; 代码实现 3. 最长连续序列题目描述解题思路关键思路#xff1a;… 哈希 1. 两数之和题目描述解题思路步骤时间复杂度空间复杂度 代码实现 2. 字母异位词分组题目描述解题思路步骤时间复杂度空间复杂度 代码实现 3. 最长连续序列题目描述解题思路关键思路步骤时间复杂度空间复杂度 代码实现 1. 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target在数组中找出两个数字使它们的和为目标值 target。你需要返回这两个数字的下标。
注意:
你可以假设每个输入只会有一个答案并且你可以按任意顺序返回答案。不允许使用循环外的额外空间且时间复杂度必须是 O(n)。
解题思路
为了高效地找到目标值 target 的两个数字采用了哈希表来存储遍历过程中遇到的数字及其对应的索引。
步骤 初始化哈希表 我们使用一个哈希表 hashTable 来存储数组 nums 中每个数字及其对应的索引。哈希表的 key 为数字value 为该数字在数组中的索引。 遍历数组 我们遍历数组 nums对于每个元素 nums[i]检查哈希表中是否存在一个元素使得 nums[i] 和该元素的和为 target。 具体来说我们检查哈希表中是否包含 target - nums[i]。如果存在说明我们找到了两个数字它们的和为 target返回它们的下标。 更新哈希表 如果当前数字 nums[i] 与之前的数字不能组成目标和则将 nums[i] 和它的下标 i 存入哈希表继续查找。 返回结果 如果找到了满足条件的两个数字就返回它们的下标如果遍历结束后仍未找到则返回空数组。
时间复杂度
遍历一次数组查找哈希表的操作时间复杂度为 O(1)因此总的时间复杂度为 O(n)其中 n 为数组的长度。
空间复杂度
我们使用了一个哈希表来存储数组元素和其下标哈希表的大小最多为数组的长度因此空间复杂度为 O(n)。
代码实现
class Solution {public int[] twoSum(int[] nums, int target) {// 使用hashMapInteger, Integer hashTable new HashMapInteger, Integer();for(int i 0; i nums.length; i) {// 检查 target - nums[i] 是否在哈希表中if(hashTable.containsKey(target - nums[i])){return new int[]{hashTable.get(target - nums[i]), i};}// 将当前数字和其下标放入哈希表hashTable.put(nums[i], i); }return new int[0]; // 如果没有找到返回空数组}
}2. 字母异位词分组
题目描述
给定一个字符串数组 strs将字符串按字母异位词Anagram进行分组。字母异位词是指两个字符串中包含的字符完全相同且字符的顺序不同。
例如eattea和 ate 是字母异位词。要求将这些字母异位词分到同一组中。
注意
输入的字符串只包含小写字母。需要将所有字母异位词按顺序返回。
解题思路
为了将字母异位词分组我们可以利用字符串的字母排序特性对于字母异位词它们的排序结果是相同的。我们可以通过对字符串进行排序将字母异位词映射到相同的键上进而将它们分到同一组。
步骤 定义哈希表 使用一个哈希表 map其键是排序后的字符串值是一个包含所有字母异位词的列表。 遍历字符串数组 对于每个字符串将其转化为字符数组并进行排序得到一个排序后的字符串。这个排序后的字符串作为哈希表的键。 存入哈希表 查找哈希表中是否已经存在该键。如果存在就将该字符串加入对应的列表如果不存在则在哈希表中创建一个新的列表并添加该字符串。 返回结果 最后哈希表中存储了所有的字母异位词分组直接返回哈希表的所有值。
时间复杂度
对于每个字符串我们将其转化为字符数组并进行排序排序的时间复杂度为 O(m log m)其中 m 是字符串的长度。遍历字符串数组的时间复杂度为 O(n)其中 n 是字符串数组的长度。因此总的时间复杂度为 O(n * m log m)其中 n 是字符串数组的长度m 是字符串的平均长度。
空间复杂度
哈希表存储了所有的字符串及其对应的字母异位词因此空间复杂度为 O(n * m)其中 n 是字符串数组的长度m 是字符串的平均长度。
代码实现
class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMap();for (String str : strs) {// 将字符串转换为字符数组并排序char[] strArray str.toCharArray();Arrays.sort(strArray);// 使用排序后的字符串作为键String key new String(strArray); // 获取或创建该键的对应列表ListString list map.getOrDefault(key, new ArrayListString());// 将当前字符串添加到列表中list.add(str);// 更新哈希表中的列表map.put(key, list);}// 返回哈希表的所有值即字母异位词分组return new ArrayListListString(map.values());}
}3. 最长连续序列
题目描述
给定一个无序的整数数组 nums返回其中最长的连续元素序列的长度。
要求你必须设计时间复杂度为 O(n) 的算法解决此问题。
解题思路
该题要求我们找到一个无序数组中的最长连续子序列。为了满足 O(n) 的时间复杂度不能采用排序的方式因为排序的时间复杂度为 O(n log n)。我们可以使用哈希集合Set来解决这个问题。
关键思路 使用哈希集合存储数组元素 将数组中的每个元素加入哈希集合中能够在 O(1) 的时间内判断某个元素是否存在。 只从连续序列的第一个元素开始搜索 遍历集合时对于每个数字 num我们只在 num-1 不在集合中的时候开始查找连续序列的长度。这样做可以避免重复计算例如当处理到序列中的中间元素时已经遍历过它前面的元素。 扩展连续序列 对于每个有效的起点 num我们尝试通过 num1、num2 等找到该序列的最大长度。 更新结果 每次找到一个新的序列更新当前最长的连续序列的长度。
步骤
将数组元素加入哈希集合 set 中。遍历集合对于每个元素 num 如果 num-1 不在集合中说明 num 是某个连续序列的起点。向右扩展检查 num1 是否在集合中直到不再连续为止。更新最长连续序列的长度。
时间复杂度
将所有元素加入集合需要 O(n) 时间。遍历数组时每个元素最多会被处理一次因此总的时间复杂度为 O(n)。
空间复杂度
哈希集合存储了所有数组元素因此空间复杂度为 O(n)。
代码实现
class Solution {public int longestConsecutive(int[] nums) {// 使用哈希集合存储数组元素SetInteger set new HashSet();for (int num : nums) {set.add(num);}int longest 0;// 遍历数组中的每个元素for (int num : set) {// 如果 num-1 不在集合中说明 num 是一个连续序列的起点if (!set.contains(num - 1)) {int currentNum num;int currentLong 1;// 向右扩展寻找连续的数字while (set.contains(currentNum 1)) {currentLong;currentNum;}// 更新最长连续子序列的长度longest Math.max(longest, currentLong);}}return longest;}
}
