做网站最清晰的字体,建设九九网站,做网站怎么做付费推广,网站服务器租用价格 百度一下hash表/map
1. 1. 两数之和
简单
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会对应一个答案#xff0c;并且你不能使用两次相同的元素。 …hash表/map
1. 1. 两数之和
简单
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]提示
2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案 class Solution { public: vectorint twoSum(vectorint nums, int target) { // 创建一个哈希表unordered_map用于存储数组元素及其索引 unordered_mapint, int unmap; // 遍历数组中的每个元素 for(int i 0; i nums.size(); i){ // 查找是否存在一个元素使得当前元素与之的和等于目标值 auto ite unmap.find(target - nums[i]); if(ite ! unmap.end()){ // 如果找到这样的元素返回当前索引和找到的索引 return {i, unmap[target - nums[i]]}; } // 将当前元素及其索引插入到哈希表中 unmap.insert(pairint, int(nums[i], i)); } // 如果没有找到符合条件的元素返回空数组 return {}; } }; 解释 unmap.find(target - nums[i]) 的返回类型是 unordered_mapint, int::iterator。这个迭代器指向哈希表中与 target - nums[i] 相等的键值对或者如果没有找到这样的键则指向 unmap.end()。
使用 auto 可以让代码更简洁和易读。
2. 49. 字母异位词分组
中等
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]
示例 2:
输入: strs []
输出: [[]]示例 3:
输入: strs [a]
输出: [[a]]提示
1 strs.length 1040 strs[i].length 100strs[i] 仅包含小写字母 class Solution { public: // 函数定义输入字符串数组返回分组的异位词 vectorvectorstring groupAnagrams(vectorstring strs) { vectorvectorstring ss; // 用于存储最终结果的二维向量 unordered_mapstring, vectorstring m; // 哈希表键为排序后的字符串值为异位词的向量 // 遍历输入的字符串数组 for(string s : strs){ string t s; // 复制当前字符串 sort(t.begin(), t.end()); // 对字符串进行排序以便找到异位词 // 将原始字符串加入到对应排序后的键的向量中 m[t].push_back(s); } // 遍历哈希表将每个值向量添加到结果中 for(auto it m.begin(); it ! m.end(); it){ ss.push_back(it-second); // 将当前异位词组添加到结果向量中 } return ss; // 返回分组后的异位词 } }; 解释
sort(s.begin(), s.end()); 这意味着所有异位词如 tea 和 ate在排序后都会转换为相同的字符串aet。
3. 128. 最长连续序列
中等
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9提示
0 nums.length 105-109 nums[i] 109 class Solution { public: int longestConsecutive(vectorint nums) { sort(nums.begin(), nums.end(), less()); // 对数组进行排序 int leng 1; // 当前连续序列的长度 int answer nums.size() 0 ? 1 : 0; // 如果数组不为空初始化为 1否则为 0 for (int i 1; i nums.size(); i) { // 跳过重复的元素 while (i nums.size() nums[i] nums[i - 1]) { i; } // 检查当前元素是否与前一个元素连续 if (i nums.size() nums[i] nums[i - 1] 1) { leng; // 增加当前连续序列的长度 answer max(answer, leng); // 更新最长连续序列的长度 } else { leng 1; // 重置当前连续序列的长度 } } return answer; // 返回最长连续序列的长度 } }; 解释
跳过重复元素的主要目的是确保在计算连续序列的长度时每个数字只被计数一次。否则重复的元素会导致错误的序列长度计算。
比如数组[1,0,1,2],正确输出为3。当经过排序后数组为[0,1,1,2],如果去掉跳过重复元素步骤则会从最后一个重复元素重新开始计数就会得到错误的答案。
1. while 循环中的条件限制
代码示例
while (i nums.size() nums[i] nums[i - 1]) { i; }
原因
当数组中有多个重复元素时i 会增加可能会最终达到 nums.size()。如果不进行边界检查访问 nums[i] 时会导致越界错误。
2. if 语句中的条件限制
代码示例
if (i nums.size() nums[i] nums[i - 1] 1) { ... }
原因
如果 while 循环已经将 i 增加到 nums.size()那么访问 nums[i] 会导致越界。这个条件确保在进行连续性检查时i 仍在有效范围内。
