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

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

1 哈希表理论基础

1.1 哈希表的内部实现原理

（1）定义与基本概念

哈希表（散列表） 是一种数据结构，它使用哈希函数将键（key）映射到数组的一个索引位置，并在该位置存储值（value），这种结构使得数据的查找、插入和删除操作非常高效。

（2）数组结构

哈希表通常基于数组实现，这个数组包含了一系列的“桶”或“槽”，每个桶可以存储一个或多个键值对，当插入一个键值对时，哈希函数计算键的哈希码，并将其转换为数组索引，然后值存储在这个索引对应的位置。

（3）时间复杂度

在最佳情况下（即没有哈希碰撞的情况），哈希表的查找、插入和删除操作的时间复杂度为O(1)。这意味着无论哈希表中存储了多少数据，这些操作的速度都是相同的。

下面是王道书上面对散列表的定义说明：

1.2 哈希函数

（1）设计原则

一个好的哈希函数应当满足以下原则：

• 均匀分布：它应该将键均匀地分布在哈希表中，以减少碰撞的机会。
• 减少冲突：尽管哈希冲突不可避免，但好的哈希函数应该尽量减少这种情况的发生。
• 计算效率高：哈希函数应该快速计算，以保持整个哈希表操作的效率。

（2）函数类型

• 直接定址法

  直接取关键字的某个线性函数值为散列地址，散列函数为：H(key) = key或H(key)= axkey + b，式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

• 除留余数法

  这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为H(key) = key % p，除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址，从而尽可能减少冲突的可能性。

• 数字分析法

  设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等;而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

• 平方取中法

  顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好。在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但目标是尽量降低产生冲突的可能性。

1.3 哈希碰撞及其解决方案

（1）哈希碰撞定义

哈希碰撞 发生在两个不同的键通过哈希函数映射到同一个索引位置时。由于哈希表的大小有限，而可能的键的数量几乎是无限的，因此哈希碰撞是不可避免的。

（2）解决方案

链地址法（Separate Chaining）：

• 在这种方法中，每个数组元素（桶）存储了一个链表。
• 当发生哈希碰撞时，冲突的元素被添加到同一索引位置的链表中。
• 这种方法可以容纳多个具有相同哈希值的键，但可能会导致链表变长，从而影响查找效率。

开放寻址法（Open Addressing）：

• 当碰撞发生时，这种方法会寻找另一个空闲的桶来存储新的键值对。
• 主要变种包括：
  • 线性探测：顺序查找下一个空闲位置。
  • 二次探测：使用二次函数确定下一个位置，以避免线性探测的聚集问题。
  • 双重散列：使用第二个哈希函数来决定搜索间隔。
• 开放寻址法易于实现，但当哈希表接近满载时，性能会下降。

（3）性能分析

• 链地址法 适合于哈希表负载因子较高（即元素较多）的情况，因为它可以通过链表容纳更多元素。但是，查找时间可能会因为链表长度的增加而增加。
• 开放寻址法 适合于元素数量较少、负载因子较低的哈希表，因为它不需要额外的内存空间来存储链表。但是，当表接近填满时，查找合适的空闲位置可能变得困难，导致性能下降。

1.4 常见哈希表的类型与区别

（1）数组（Array-based Hash Table）

• 定义：使用索引作为键，通常用于固定大小的数据集。
• 应用场景：适用于数据量已知且变化不大的场景，如用于存储预定义数量的元素。

（2）集合（Set）

• 定义：存储唯一元素的数据结构，不允许重复。
• 应用场景：常用于去重和存在性检测，例如在一组数据中检查某个元素是否存在。

（3）映射（Map）

• 定义：存储键值对的数据结构，提供基于键的灵活数据访问。
• 应用场景：适用于需要关联键和值并频繁检索的情况，如数据库的索引或缓存系统。

下面表格说明了数组、集合和映射的实现差异和使用场景：

数据结构类型	内部结构	使用场景
数组	基于索引访问	当需要通过索引快速访问元素时，适用于数据量已知且变化不大的场景。
集合	使用哈希表实现，仅存储键	当需要存储不重复的元素，主要关心元素的存在性而不是其特定的值时。
映射	使用哈希表实现，存储键值对	当需要建立键和值之间的关联，并且经常根据键来检索值时。

2 LeetCode 242.有效的字母异位词

题目链接：https://leetcode.cn/problems/valid-anagram/

给定两个字符串 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 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

出现要我们快速判断一个元素是否出现集合里的时候，我们就可以考虑用哈希法，就像是条件反射一样，就像是我们之前练习双指针法一样，出现需要同时考虑两个不同位置元素的的时候我们就可以考虑双指针法，不同的算法都有其特定的场景应用，我们需要记住这些。

回到这道题目，题目要求我们判断两个字母字符串中各种字母出现的频率是否一致，而且告诉我们s 和 t 仅包含小写字母，我们可以定义一个数组用来存放我们遍历出来的字母次数，然后我们就需要考虑定义的数组大小多少最好，因为仅包含小写字母，因此我们就可以只定义一个长度为26的数组，每个字母对应数组的一个位置。

通过遍历字符串，依次判断字母是否出现过，若出现则在对应数组位置+1，遍历完第一个字符串我们就可以知道出现过了多少字母以及其出现的次数，那么如何判断两个字符串是否为字母异位词，我们就需要对另一个字符串做逆运算，也就是在遍历第二个字符串时对出现过的字母其位置数值-1，这样在遍历完两个字符串之后我们只需要通过判断我们定义的数组每一个位置是否都为0就可以判断出来，因为它们对应位置的值互相抵消了，也就代表两个字符串出现的字母一样其对应出现的次数也一样，即互为字母异位词。

理论清楚，现在我们来实操代码。

（1）Python版本代码：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26   # 用于记录26个字母出现的次数
        for i in range(len(s)): # 遍历s字符串，记录每个字母出现的次数
            record[ord(s[i]) - ord('a')] += 1   # ord()函数返回字符的ASCII码
        for i in range(len(t)): # 遍历t字符串，将每个字母出现的次数减1
            record[ord(t[i]) - ord('a')] -= 1
        for i in range(26): # 遍历26个字母
            if record[i] != 0:  # 如果某个字母的出现次数不为0，返回False
                return False
        return True # 如果所有字母的出现次数都为0，返回True
    
if __name__ == "__main__":
    s = input()
    t = input()
    solution = Solution()
    print(solution.isAnagram(s, t))

（2）C++版本代码

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    bool isAnagram(std::string s, std::string t) {
        // 如果s和t的长度不同，它们一定不是异位词
        if (s.length() != t.length()) {
            return false;
        }
        std::vector<int> record(26, 0); // 用于记录26个字母出现的次数
        for (int i = 0; i < s.length(); i++) { // 遍历s字符串，记录每个字母出现的次数
            record[s[i] - 'a']++; // ord()在C++中是直接使用字符的ASCII码
        }
        for (int i = 0; i < t.length(); i++) { // 遍历t字符串，将每个字母出现的次数减1
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) { // 遍历26个字母
            if (record[i] != 0) { // 如果某个字母的出现次数不为0，返回False
                return false;
            }
        }
        return true; // 如果所有字母的出现次数都为0，返回True
    }
};

int main() {
    Solution solution;
    std::string s, t;
    std::cin >> s >> t;
    std::cout << (solution.isAnagram(s, t) ? "True" : "False") << std::endl;
    return 0;
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

3 LeetCode 349.两个数组的交集

题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/description/

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

题目要求：输出结果中的每个元素一定是 唯一 的，而且还是求交集，这已经在疯狂暗示你用集合来解决，集合是有去重的功能的，刚好就可以解决这道题目，而且这题也可以使用数组做哈希表，因为给你限制了数组大小，不是很大（一般题目给你限制了数组大小就可以使用，如果数组大小没有限制则不推荐，因为空间复杂度会很高）因此我们既可以使用集合也可以使用数组来解决。

下面我们来尝试两种写法：

（1）Python版本代码：

• 集合

  class Solution:
      def intersection(self, nums1, nums2):
          set1 = set(nums1)   # 将nums1转换为集合
          set2 = set(nums2)   # 将nums2转换为集合
          
          return list(set1 & set2)    # 返回两个集合的交集
      
  if __name__ == "__main__":
      nums1 = list(map(int, input().split()))
      nums2 = list(map(int, input().split()))
      solution = Solution()
      print(solution.intersection(nums1, nums2))
  

  • 时间复杂度：O(N + M)，其中 N 是 nums1 的长度，M 是 nums2 的长度。
  • 空间复杂度：O(N + M)

• 数组

  class Solution:
      def intersection(self, nums1, nums2):
          # 假设元素范围在0到1000之间
          hash_table = [0] * 1001
          result = []
  
          # 对nums1中的每个元素在哈希表中做标记
          for num in nums1:
              hash_table[num] = 1
  
          # 遍历nums2，检查元素是否在nums1中出现过
          for num in nums2:
              if hash_table[num] == 1:
                  result.append(num)
                  hash_table[num] = 0  # 避免重复添加
  
          return result
      
  if __name__ == "__main__":
      nums1 = list(map(int, input().split()))
      nums2 = list(map(int, input().split()))
      solution = Solution()
      print(solution.intersection(nums1, nums2))
  

  • 时间复杂度：O(N + M)

  • 空间复杂度：O(1001)，也即O(1)

  • 使用数组方法的优点是减少了使用集合操作所需的额外空间，特别是当两个数组的大小差异很大时更为高效。

（2）C++版本代码：

• 集合：

  #include <iostream>
  #include <vector>
  #include <unordered_set>
  #include <algorithm>
  
  class Solution {
  public:
      std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
          std::unordered_set<int> set1(nums1.begin(), nums1.end()); // 将nums1转换为集合
          std::unordered_set<int> set2(nums2.begin(), nums2.end()); // 将nums2转换为集合
          std::vector<int> result;
  
          for (auto num : set1) {
              if (set2.find(num) != set2.end()) { // 如果在set2中找到了num
                  result.push_back(num);
              }
          }
          return result; // 返回两个集合的交集
      }
  };
  
  int main() {
      Solution solution;
      std::vector<int> nums1, nums2;
      int num;
  
      // 读取nums1
      while (std::cin >> num) {
          nums1.push_back(num);
          if (std::cin.peek() == '\n') break;
      }
  
      // 读取nums2
      while (std::cin >> num) {
          nums2.push_back(num);
          if (std::cin.peek() == '\n') break;
      }
  
      std::vector<int> result = solution.intersection(nums1, nums2);
      for (auto num : result) {
          std::cout << num << " ";
      }
      return 0;
  }
  

• 数组：

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  class Solution {
  public:
      std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
          std::vector<int> hash_table(1001, 0); // 假设元素范围在0到1000之间
          std::vector<int> result;
  
          // 对nums1中的每个元素在哈希表中做标记
          for (auto num : nums1) {
              hash_table[num] = 1;
          }
  
          // 遍历nums2，检查元素是否在nums1中出现过
          for (auto num : nums2) {
              if (hash_table[num] == 1) {
                  result.push_back(num);
                  hash_table[num] = 0; // 避免重复添加
              }
          }
          return result;
      }
  };
  
  int main() {
      Solution solution;
      std::vector<int> nums1, nums2;
      int num;
  
      // 读取nums1
      while (std::cin >> num) {
          nums1.push_back(num);
          if (std::cin.peek() == '\n') break;
      }
  
      // 读取nums2
      while (std::cin >> num) {
          nums2.push_back(num);
          if (std::cin.peek() == '\n') break;
      }
  
      std::vector<int> result = solution.intersection(nums1, nums2);
      for (auto num : result) {
          std::cout << num << " ";
      }
      return 0;
  }
  

4 LeetCode 202.快乐数

题目链接：https://leetcode.cn/problems/happy-number/description/

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

解决这道题目的关键是检测sum的变换过程中是否出现循环，如果出现循环，且循环中不包含 1，则该数字不是快乐数，因此我们就可以考虑使用哈希表来解决，使用 哈希集合 来存储所有已经出现过的数字，在每次变换过程中，如果新计算出的数字已经在哈希集合中，说明发生了循环，这时可以判断该数不是快乐数，否则就是，我们需要对数字进行分解，也就是计算其各个位上数字的平方和，然后检查新计算出的数字是否为 1 或者是否已经出现过，如果没有出现循环，也没有得到 1，则继续下一步分解再循环。

（1）Python版本代码

class Solution:
    def isHappy(self, n: int) -> bool:
        def getSum(n):      # 计算n的各位数字的平方和
            sum = 0
            while n > 0:        # 当n大于0时，不断取n的个位数，计算平方和
                sum += (n % 10) ** 2    # n % 10取n的个位数
                n = n // 10             # n // 10取n的十位数及以上
            return sum
        record = set()      # 记录出现过的数字
        while n != 1:        # 当不为1时
            if n in record:      # 如果出现过则返回False
                return False    
            record.add(n)       # 记录      
            n = getSum(n)
            
        return True

if __name__ == "__main__":
    n = int(input())
    solution = Solution()
    print(solution.isHappy(n))

• 时间复杂度：O(log n)，因为每次迭代都会减少数字的大小。
• 空间复杂度：O(log n)，用于存储中间出现的数字。

（2）C++版本代码

#include <iostream>
#include <unordered_set>
using namespace std;

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;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

int main() {
    Solution solution;
    int n;
    cout << "输入一个数字：";
    cin >> n;
    bool result = solution.isHappy(n);
    cout << (result ? "True" : "False") << endl;
    return 0;
}

5 LeetCode 1.两数之和

题目链接：https://leetcode.cn/problems/two-sum/

给定一个整数数组 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
• 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

本题可以算是梦开始的地方，因为是力扣题库的第一道题目，我们的刷题之旅基本上都是从这题开始的，一脸懵逼的开始刷题，然后一脸懵逼的离开，所以有人说：有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

这道题目我们可以首先直接暴力枚举解决，两层for循环把数组遍历然后每一种情况都相加存入一个变量sum中，然后判断sum是否等于target即可，非常的简单。

5.1 暴力枚举法

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):  # 遍历nums
            for j in range(len(nums)):              
                sum = nums[i] + nums[j] 
                if sum == target:
                    return [i, j]
                
if __name__ == "__main__":
    nums = list(map(int, input().split()))
    target = int(input())
    solution = Solution()
    print(solution.twoSum(nums, target))

很明显时间复杂度是O($n^2$)。

5.2 哈希法

我们知道哈希法的类型有三种：数组，集合以及映射，这三种类型的选择并不是随心所欲的，我们需要了解题目为什么要选什么类型，为什么不能选什么类型，想要写出一个好的算法，必不可少的就要首先选择一个好的数据结构类型，那么对于本题来说，我们选择映射（map）要更适合一点。

• 为什么不选择集合（Set）？

  集合（Set）是一个存储唯一元素的数据结构，它优秀于快速查找元素是否存在，然而对于这个特定问题，“两数之和”，我们需要的不仅是判断某个值是否存在，还需要知道该值的索引，而集合不保存任何有关元素位置或索引的信息，所以它不适用于这个问题。

• 为什么不选择数组（Array）？

  虽然原始数据就是以数组的形式给出的，但数组不适合用来解决这个问题，主要因为它在查找特定值时的效率不够高，如果使用数组，我们通常需要两层循环遍历整个数组来找出满足条件的一对数字，这样的解决方案的时间复杂度是 O(n2)，对于大数据集来说效率较低。

• 为什么选择映射（Map）？

  • 快速查找：哈希表支持以接近 O(1) 的时间复杂度进行查找操作，这比数组的线性查找快得多。
  • 存储额外信息：哈希表不仅可以存储值，还可以存储与值相关的额外信息，比如该值在数组中的索引，这意味着我们可以一边遍历数组，一边将元素值及其对应的索引存储在哈希表中，在遍历过程中，我们可以快速检查哈希表里是否存在与当前元素配对的目标值。

搞清楚我们为什么要选择映射这种数据结构之后，我们就可以开始写代码了。

（1）Python版本代码

class Solution:
    def twoSum(self, nums, target):
        # 创建哈希表用于存储已经遍历过的数字及其索引
        hash_table = {}
        for i, num in enumerate(nums):
            complement = target - num       # 计算配对的数字
            if complement in hash_table:    # 检查配对数字是否已经在哈希表中
                return [hash_table[complement], i]       # 如果配对数字已存在，返回当前数字的索引和配对数字的索引
            hash_table[num] = i     # 如果配对数字不存在，将当前数字及其索引存入哈希表
        return []       # 如果没有找到配对的数字，返回空列表

（2）C++版本代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        // 创建哈希表用于存储已经遍历过的数字及其索引
        std::unordered_map<int, int> hash_table;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i]; // 计算配对的数字
            // 检查配对数字是否已经在哈希表中
            if (hash_table.find(complement) != hash_table.end()) {
                // 如果配对数字已存在，返回当前数字的索引和配对数字的索引
                return {hash_table[complement], i};
            }
            // 如果配对数字不存在，将当前数字及其索引存入哈希表
            hash_table[nums[i]] = i;
        }
        // 如果没有找到配对的数字，返回空列表
        return {};
    }
};

int main() {
    Solution solution;
    std::vector<int> nums;
    int target;
    std::string line;

    std::cout << "输入数字数组，以空格分隔：" << std::endl;
    std::getline(std::cin, line);
    std::istringstream stream(line);
    int number;
    while (stream >> number) {
        nums.push_back(number);
    }

    std::cout << "输入目标值：" << std::endl;
    std::cin >> target;

    std::vector<int> result = solution.twoSum(nums, target);
    std::cout << "结果：";
    for (int i : result) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)