代码随想录算法训练营第六天 | 242. 有效的字母异位词 349.两个数组的交集 202. 快乐数 1.两数之和

有效的字母异位词

思路：

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public:
      bool isAnagram(string s, string t) {
          int record[26] = { 0 };
          for (int i = 0; i < s.size(); i++) {
              record[s[i] - 'a']++;
          }
          for (int i = 0; i < t.size(); i++) {
              record[t[i] - 'a']--;
          }
          for (int i = 0; i < 26; i++) {
              if (record[i] != 0) {
                  return false;
              }

          }
          return true;
      }
  };

两个数组的交集

思路：

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序

这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。

那么用数组来做哈希表也是不错的选择，例如242. 有效的字母异位词(opens new window)

但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

std::set
std::multiset
std::unordered_set
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
  public:
      vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
          unordered_set<int> result_set;
          unordered_set<int> nums_set(nums1.begin(), nums1.end());
          for (int num : nums2) {
              if (nums_set.find(num) != nums_set.end()) {
                  result_set.insert(num);
              }
          }
          return vector<int>(result_set.begin(), result_set.end());
      }
  };

补充（用数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话，result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

注释：

1.unordered_set nums_set(nums1.begin(), nums1.end()) 是使用迭代器范围初始化 nums_set 对象的方式。在这里，nums1.begin() 返回 nums1 容器中第一个元素的迭代器，nums1.end() 返回 nums1 容器中最后一个元素之后的迭代器（即末尾迭代器）。
通过将迭代器范围作为参数传递给 unordered_set 的构造函数，可以将 nums1 容器中的元素插入到新创建的 nums_set 集合中。这样就实现了将一个容器中的元素复制到另一个无序集合中的功能。
具体来说，nums_set(nums1.begin(), nums1.end()) 的作用是将 nums1 容器中的所有元素复制到一个新的 unordered_set 对象 nums_set 中。这样，在后续的代码中，我们就可以使用 nums_set 来快速查找元素是否存在，而无需遍历整个数组。
2.for (int num : nums2) 是 C++11 中引入的 range-based for 循环，也叫 foreach 循环，用于遍历容器中的元素。
具体来说，这个循环的语法是：for ( element : container )，其中 element 是容器中元素的类型，container 则是一个支持迭代器的容器对象，包括 vector、array、list、set、map 等等。
在每次循环中，element 将被自动赋值为 container 中的下一个元素。这样就可以方便地遍历整个容器，而不需要使用迭代器。
在这段代码中，for (int num : nums2) 的作用是遍历 nums2 容器中的所有元素，并将每个元素赋值给 num 变量。通过这种方式，我们可以逐个处理 nums2 中的元素，实现对数组的遍历和操作。
3.nums_set.find(num) != nums_set.end() 是用于判断 num 是否在 nums_set 中的条件语句。
在 unordered_set 中，find() 函数用于查找指定元素是否存在，并返回指向该元素的迭代器。如果元素存在，返回指向该元素的迭代器；如果不存在，返回一个指向 end() 的迭代器。
因此，nums_set.find(num) 将返回一个迭代器，如果 num 存在于 nums_set 中，那么该迭代器将指向 num；如果不存在，该迭代器将指向 nums_set.end()。
所以，nums_set.find(num) != nums_set.end() 的判断表达式实际上是判断 num 是否在 nums_set 中。如果返回值为 true，表示 num 存在于集合中；如果返回值为 false，表示 num 不存在于集合中。
在代码中，这个条件语句用于判断 nums2 中的元素是否同时存在于 nums1 中，如果存在，则将该元素插入到 result_set 中。这样就实现了求两个数组的交集的功能。

快乐数

思路：

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

正如：关于哈希表，你该了解这些！ (opens new window)中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while (1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            if (set.find(sum) != set.end()) {
                return false;
            }
            else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

两数之和

思路：

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++){
            auto iter = map.find(target - nums[i]);
            if (iter != map.end()) {
                return{ iter->second,i };
            }
            map.insert(pair<int, int>(nums[i], i));
        }
        return {};
    }
};

在这段代码中，pair<int, int>(nums[i], i) 是创建一个键值对的方式。pair 是 C++ 标准库中的一个模板类，用于存储一对值。它包含两个成员变量 first 和 second，分别表示键和值。
所以，pair<int, int>(nums[i], i) 创建了一个整型键值对，其中 nums[i] 是键，i 是值。然后，通过 map.insert() 函数将这个键值对插入到哈希映射 map 中，以便之后可以通过键来查找对应的值。
简而言之，pair 的作用是将两个值作为一个整体进行存储和操作，用于表示键值对关系。