【算法练习Day5】有效的字母异位词 &两个数组的交集&&快乐数&&两数之和

​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

这篇博客主要是针对于哈希表的应用内容。哈希表主要分为三种哈希结构：数组，set和map。哈希表的应用主要在于解决一些，需要查找某个元素是否出现过的问题，需要快速查找类问题，可以优先考虑使用哈希表，它的查找时间为O(1)

通常情况，我们在想要一个数据元素差别小，且元素较少的集合时，优先选择数组，它的特点是比set和map存储空间上简单一些，查找数据较快。而面对一些数据元素相差大，且元素数据值较大，或数值多，可以考虑set，无序时预先考虑unordered_set，它是哈希结构实现的，比红黑树实现的set和muliti_set更快。在需要做数据映射也就是同时存储一对有关联的元素时用map。

有效的字母异位词

242. 有效的字母异位词 - 力扣（LeetCode）

这是用数组做哈希的经典题目，选用数组作为哈希结构的理由是，该题判断两字符串的相同字母出现频率是否相同，而小写字母一共只有26个，数据少且连续，所以选用数组。

解题思路为：哈希表26个字母的位序依次对应于数组的0-25的下标，且一开始均为0，分别遍历两个字符串，对于第一个字符串的每一个字母减去字符‘a’，所得到的就是它当前在哈希表中对应的位置，该字母每出现一次，将该位置数值自增1。遍历第二个字符串就是自减1，和前面处理是相同的方法，处理完之后，若哈希表内0-25位置的元素值均为0，那么说明此时两字符串的字母出现频率相等，如果不为0则直接返回false。

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']++; // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
        }
        for(int j=0;j<t.size();j++)
        {
            record[t[j]-'a']--;
        }
        for(int k=0;k<26;k++)
        {
           if(record[k]!=0)// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
           {
               return false;
           }
        }
        return true;// record数组所有元素都为零0，说明字符串s和t是字母异位词
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

● 为什么遍历第二个字符串时只考虑碰到计数小于0的情况返回false而不考虑大于0的情况（即s字符串出现了t字符串中没有的字符）？
最开始会判断两个字符串长度是否相等，在两个字符串长度相同的情况下，如果有大于0的情况，一定对应地会出现其他字符小于0。

两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

这道题，也可以用数组来做哈希，且运行效率很高，但是由于此题在未更改题目描述和测试用例时，是没有给定具体的数组长度的，所以用set

具体思路为：定义两个无序set，由于判断两个数组交集返回的数据可以忽略数据的顺序，所以可以使用无序set来提高运行速度。第一个set用来存储第一个数组的所有元素(由于set的特点数组中有重复元素并不会重复存放)，存储完之后，遍历第二个数组，用find成员函数来查找该set里有没有和其相同的元素出现，若有则放到第二个set里，同样该set也是可以去重的，最后返回的vector里的元素用第二个set来填充即可。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) 
        {
            // 发现nums2的元素 在nums_set里又出现过
            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
17

当然用数组来做哈希结构也是可以的，这里只提供思路：用数组哈希来存储nums1中每个数出现的频率，再判断该哈希中的数是否在nums2里也出现过，将值传进set内，完成后return。

快乐数

202. 快乐数 - 力扣（LeetCode）

快乐数是求一个数的每一位求平方和，最后经过这样的若干次变化后是否等于1。

解题思路的要点是用set来存储这些中间变化的平方和值，那么为什么要这样做呢？一个数只分为经过变化后平方和等于1循环，和经过变化后平方和变成某些数字的死循环两种。所以用哈希存储变化中的数值至关重要。由于不知道该数要变换几次，可能次数很多需要存储数据很多，所以采用set来做哈希。

代码如下

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;
        }
    }
};
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
28
29
30
31
32
33
34
35
36

当判断中取得的平方和在set中已经被取到，则直接返回false。

另一种思路是leetcode官方给出的，双指针方法，很巧妙。

思路是：创建slow和fast两个变量，起初都等于数字n，然后用平方和函数调用一下，slow调用一次，fast调用两次，最终无论是什么结果两指针都会相遇，即指向相同的数字，如果是结果为1结束的，那么1的平方和无论怎么加都是1，如果是一些数的循环，可以把它想象为一个环形链表，在固定的一些数里循环，总有slow和fast相等的情况。出循环时判断一个指针是否等于1就可以了。

class Solution {
public:
    bool isHappy(int n) 
    {
        int slow=n;int fast=n;
        do{
            slow=get(slow);
            fast=get(fast);
            fast=get(fast);
        }
        while(slow!=fast);
        
        return (slow==1);
    }
    int get(int n)
    {
        int sum=0;
        while(n)
        {
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
};
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

● sum重复出现，就肯定不是快乐数，为什么呢？
因为只要重复出现一次就说明会无限循环，就像之前链表那个环，假设a1算完等于a2,a2算完等于a3，a3算完等于a1，那么下一次a1算完必定等于a2，再下一次a2算完必定是a3，形成了一个循环，而这个循环中不可能有1，因为1平方的结果永远是1,所以肯定有循环就肯定不是快乐数

两数之和

1. 两数之和 - 力扣（LeetCode）

这道题基本是每个刷leetcode的第一道题，我最开始做这道题时候，只写出了一个暴力解法，而且还是看题解写的。暴力的思路简单一些就是两个循环，第一个数和剩下的数相加，第二个数和剩下的数相加，以此类推。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       vector<int>result;
       for(int i=0;i<nums.size();i++)
       {
       	for(int j=i+1;j<nums.size();j++)
       	{
           if(nums[i]+nums[j]==target)
           {
               result.push_back(i);
               result.push_back(j);
           }
       } 
      return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二种方法就是使用哈希法中的map存储结构，为什么用map呢？思路是这样的，我们将数组中已经遍历过的数用map存储下来，由于我们需要返回的是数组下标，而并非是哪两个数所组成的，所以我们将map设置为key值为数组里的元素值，而value设置为数组元素对应的下标。

我们每遍历一个数就要在map里面查找，是否有可以与该数相加之后构成target的值，如果有则直接返回，没有将该数加入map，遍历下一个数，直到遍历完全，若还没有返回，则说明找不到目标数返回null。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

● 一般说数组作为哈希表 是利用值作为数组下标来达到快速定位 所以查找也能达到O(1)的复杂度 但是适用范围很有限

● 用unordered_map不是不能存储两个相同的key吗，那如果数组里两个出现相同的两个元素都要存储会怎么样呢？
注意它存入的方式，它是在循环的过程中边检验边存的，如果没有对应的数字就存入map，如果有就计数，这样不会遇到重复的

总结：

今天的四道题涉及哈希的思想，之前没有这么练习过，收获不少。接下来，我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~