第十一章

  • 有效的字母异位词
    • 题目理解
    • 代码
  • 两数之和
    • 题目理解(暴力篇)
    • 代码
    • 题目理解(哈希篇)
    • 代码

有效的字母异位词

力扣链接
给定两个字符串 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};// 如果两个数组的大小都不一样, 那就直接返回 falseif(s.size() != t.size())return false;for(int i = 0; i < s.size(); i++){sum[s[i] - 'a']++; // a数组的此字母对应的下标++sum[t[i] - 'a']--; // b数组的此字母对应的下标--}// 如果两个数组每个字符出现的次数是一样的, 每个下标对应的都是 0for(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;}};

题目理解(哈希篇)

我们就会发现, 暴力解法虽然可以, 但是执行时间很长, 那有没有执行时间短的方法呢” />

由于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 {}; }};

  • 这个题目要搞懂的四个点:
  1. 为什么要选取哈希的算法
  2. 哈希为啥要用map的数据结构
  3. map是用来干什么的
  4. map中的key是用来存放什么的, value是用来存放什么的

个人感觉, 搞懂这四个点, 那么此题目就理得条条顺顺喽!!!

人是有惰性属性的动物，一旦过多地沉湎于温柔之乡，就更削弱了重新投入风暴的勇气和力量. — — 路遥