当前位置：首页 > news >正文

哈希表- 快乐数两数之和四数相加II

news 2026/3/27 1:32:02

哈希表

快乐数（leetcode.202）

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

「快乐数」 定义为：

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

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

哈希表

快乐数，这其实也就是找是否循环的问题，首先我们需要先通过一个函数得到每个位置上的和。

从个位上开始，n % 10这个得到的就是个位上的数字了，然后我们需要将个位截断，也就是得到除了个位上的数，这其实并不难n / 10整除10就行了，这样循环就可以得到sum。

接下来是判断是否为快乐数，那么就是看是否发生循环，也就是某个元素是否重复出现，我们使用unordered_set来实现，定义一个集合，将传入的数放进集合，之后用循环开始遍历获取sum，得到sum后看看集合里有没有，有的话，那么直接返回false，如果等到满足条件了，直接退出返回true。

class Solution {
public:int getSum(int n){int sum = 0;while(n > 0){int num = n % 10;sum += num * num;n /= 10;}return sum;}bool isHappy(int n) {std::unordered_set<int> set_num;set_num.insert(n);int sum = getSum(n);while(sum != 1){if(set_num.find(sum) != set_num.end()){return false;}set_num.insert(sum);sum = getSum(sum);}return true;}
};

双指针思路

什么的思路可以知道如果不是快乐数，那么就会进入循环，那么我们可以使用双指针的思路，让快指针每次运行两次，慢指针每次运行一次，如果快指针追上了慢指针说明是循环的，就不是快乐数了。这里注意循环条件，是快指针没有到1，说明没找到，继续找，因为如果是快乐数，那么再求和，也依然是1。

bool isHappy(int n) {int fast = getSum(getSum(n));int slow = n;while(fast != 1){if(slow == fast){return false;}else if(fast == 1){return true;}slow = getSum(slow);fast = getSum(getSum(fast));}return true;}

两数之和 (leetcode.1)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

哈希表使用时机始终是一个比较难以判断的问题，什么时候使用哈希法，当查询一个元素时候出现过，或者一个元素是否在集合里，就要想到哈希法。

我们之前的有效字母异位词，我们想到哈希，我们是用数组实现的，因为字母是26个，所以定义了一个hash[26]，遍历一个字符串，可以得到每个字符的出现次数并记录到数组中，之后再遍历另一个字符串，减去之前的各个字符个数，这里是不是比对了元素是否出现？考虑哈希

两个数组的交集，我们是需要知道一个数组中元素的出现的，然后，遍历另一个数组，看看能不能找到元素，也就是元素是否在集合里？哈希

前面的快乐数，依旧是把出现的元素放进集合，判断下一次和是否出现过，出现表示进入循环不是快乐数，一个元素是否在集合，哈希

那么这里的两数之和，这里我们不但得知道这个元素是否出现过，还得知道下标，那么是不是可以通过map映射的方式。

因为是两个数，那么注意到，在遍历数组的时候，可以将元素放入unordered_map，那么得考虑key - value怎么存储了，key = 值，value = 索引，我们可以直接去找键，找到了，就直接返回索引，找不到，就存入map

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {std::unordered_map<int,int> index_num;for(int i = 0; i < nums.size(); ++i){auto it = index_num.find(target-nums[i]);if(it != index_num.end()){return {i,it->second};} else{index_num[nums[i]] = i;}}return {};}
};

四数相加II (leetcode.454)

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

解题思路
1. 将四数之和转化为两数之和
2. 先计算 A+B 的所有和及其频次
3. 遍历 C+D，查找相反数

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {std::unordered_map<int,int> sumAB;for(const auto& n1 : nums1){for(const auto& n2 : nums2){++sumAB[n1+n2];}}int count = 0;for(const auto& n3 : nums3){for(const auto& n4 : nums4){int target = -(n3+n4);auto it = sumAB.find(target);if(it != sumAB.end()){count += it->second;}}}return count;}
};

这里在总结一下哈希表核心应用场景，以空间换时间，很重要的思想

统计频次