算法模型总结：哈希

class Solution {
public:
    struct Count
    {
        int scount;
        int tcount;
        Count():scount(0),tcount(0)
        {}
    };
    bool isAnagram(string s, string t) {
        unordered_map m;
        if(s.size()!=t.size())
        {
            return false;
        }
        for(int i=0;i

• 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

2. 两个数组的交集

349. 两个数组的交集

使用和上一题一样的方法，定义一个unordered_map，第一个元素为字符，第二个元素是一个结构体，它的有两个元素，分别代表的是该字符在两个字符串中是否出现。

最后遍历这个map，如果它的结构体中的两个元素的值都是1则表示该字符为两个数组的交集。

class Solution {
public:
struct Flag
{
    int flag1=0;
    int flag2=0;
};
    vector intersection(vector& nums1, vector& nums2) {
        unordered_map m;
        for(int i=0;i result;
        for(auto& e:m)
        {
            if(e.second.flag1==1&&e.second.flag2==1)
            {
                result.push_back(e.first);
            }
        }
        return result;
    }
};
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

3.快乐数

快乐数

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

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

首先，有两种情况，要么是无限循环，要么是1。

无限循环代表着，它求的平方和一定有重复的。我们只需要将每一次求出来的平方和放在一个unordered_set中，每一次再求一个平方和后在这个set中进行查找，若找到了则有循环。若求得为1，则它是快乐数。

class Solution {
public:
int Sum(int n)
{
    int sum=0;
    int count=1;
    while(n!=0)
    {
        sum+=(n%10)*(n%10);
        n/=10;
    }
    return sum;
}
    bool isHappy(int n) {
        unordered_set s;
        int sum=Sum(n);
        while(1)
        {
        if(sum==1)
        {
            return true;
        }
        if(s.find(sum)==s.end())
        {
            s.insert(sum);
            sum=Sum(sum);
        }
        else
        {
            return false;
        }
        }
        return true;            
    }
};
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

4.四数相加

454. 四数相加 II

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

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

分为两组，每组使用一个unordered_map，它只需要计算有多少个这样的组而已。

先看前两个数相加，使用双层for循环计算所有两个数相加的值，放在map的第一个元素，该和出现的次数放在第二个元素。

再看后两个数相加，用两层for循环依次计算所有两个数的和，将它们的和取负数，在map中查找，并将找到元素的map的第二个值加到结果中。

四数相加和四数之和的区别在于，四数相加是四个数组。

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
        unordered_map m;
        int sum1=0;
        int count=0;
        for(int i=0;isecond;
                }    
            }
        }
        return count;
    }
};
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

5.赎金信

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

首先遍历magazine，使用set进行去重，然后遍历ransomNote，使用find在set中找ransonNote的每个字符，如果没找到则不能，都找完了则可以。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map m;
        for(int i=0;i0)
                {
                    m[e]--;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};
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