有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
题目理解
因为题目的要求是:
两个数组 仅仅包含小写字母 ⇒ 一共才26个英语字母
两个数组的大小是 1 <= length <= 5*10的四次方
⇒ 我们可以采用 哈希的思想
我们可以用一个数组(利用下标)来记录两个数组中每个字母出现的次数
然后通过比较 每个字母出现的次数 和 0 进行比较
🗨️那小写字母如何装换为数组下标?
通过ASCLL码来进行转化 ⇒ 字母 - 'a'
代码
class Solution { public: bool isAnagram(string s, string t) { int sum[26] = {0}; // 如果两个数组的大小都不一样, 那就直接返回 false if(s.size() != t.size()) return false; for(int i = 0; i < s.size(); i++) { sum[s[i] - 'a']++; // a数组的此字母对应的下标++ sum[t[i] - 'a']--; // b数组的此字母对应的下标-- } // 如果两个数组每个字符出现的次数是一样的, 每个下标对应的都是 0 for(int i = 0; i < 26; i++) { if(sum[i] != 0) return false; } return true; } };
两数之和
给定一个整数数组 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
只会存在一个有效答案
题目理解(暴力篇)
这题一看就是 低配版 ⇒ 2 <= size( ) <= 10^4, 这个数组的大小就是很巴适
暴力解法就是 两个for循环 ⇒ 最大时间也是 10^8, 不会爆时间的
代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> sum; for(int i = 0; i < nums.size(); i++) { for(int j = i + 1; j < nums.size(); j++) { if(nums[j] == target - nums[i]) { sum.push_back(i); sum.push_back(j); break; } } } return sum; } };
题目理解(哈希篇)
我们就会发现, 暴力解法虽然可以, 但是执行时间很长, 那有没有执行时间短的方法呢?
我们的一个思路是: 当我们顺序遍历该数组时, 当我们遍历到一个特定的下标(nums[i])时, 我们需要知道 target - nums[i] 这个数字是否在之前遍历过的数字里面出现过 如果出现 — — 返回 (target - nums[i]) 的下标 和 nums[i]的下标 (i) 如果没有出现 — — 不返回, 如果直至数组的结尾, 也没有出现, 那就返回空
当我们查询一个元素是否出现过, 或者一个元素在一个集合中是否存在 — — 那就可以使用哈希
在本题中, 我们不仅需要知道 (target - nums[i])这个数是否遍历过, 也要知道 (target - nums[i]) 的下标
⇒
那么我们就不能用数组来进行存储了, 可以采用 map的方式进行存储 (key, value)
⇒ key该存储什么, value又该存储什么呢?
由于本题需要返回的是下标, 所以 key应该存储下标, valu来存储数值
⇒ 那map有三种形式, 我们应该选取哪一种呢? map, unordered_map, multimap
由于unordered_map的查询效率是三个当中最快的, 那么我们就选用 unordered_map
代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // 选用unordered_map这个数据结构 std::unordered_map<int, int> map; for(int i = 0; i < nums.size(); i++) { // 查询 target - nums[i]是否被遍历过 auto cur = map.find(target - nums[i]); // 之前有被遍历过, 那就直接返回 if(cur != map.end()) { return {cur->second, i}; } // 没有遍历过, 那就收入map里面 map.insert(pair<int, int> (nums[i], i)); } // 最后在map里面都没有找到, 那就返回空 return {}; } };
- 这个题目要搞懂的四个点:
- 为什么要选取哈希的算法
- 哈希为啥要用map的数据结构
- map是用来干什么的
- map中的key是用来存放什么的, value是用来存放什么的
个人感觉, 搞懂这四个点, 那么此题目就理得条条顺顺喽!!!
