代码随想录算法训练营第7天｜454. 四数相加 II、383. 赎金信

454. 四数相加 II

Problem: 454. 四数相加 II

1. 思路

直接暴力的话就会有n^4的复杂度
分为两组记录值(预处理，用空间消耗来替代时间消耗)，这样就退化为两数之和了，复杂度依旧会达到n^2,不过看了一下n的取值在0～200，所以n^2还可以接受

2.复习unordered_ma的基本用法

unordered_map 是 C++ 标准库中的一个容器，它提供了存储键值对的功能，并且能够快速地根据键来查找值。它使用哈希表来实现，因此查找、插入和删除操作的平均时间复杂度为 O(1)。下面是 unordered_map 的一些基本用法：

2.1包含头文件

在使用 unordered_map 之前，需要包含头文件 <unordered_map>。

#include <iostream>
#include <unordered_map>
1
2

2.2声明

你可以像这样声明一个 unordered_map：

std::unordered_map<std::string, int> myMap;
1

这里声明了一个 unordered_map，其键类型为 std::string，值类型为 int。

2.3插入元素

有几种方法可以向 unordered_map 中插入元素：

// 使用 insert 函数插入 pair
myMap.insert(std::make_pair("apple", 1));

// 使用数组语法插入或更新
myMap["banana"] = 2;

// 使用 emplace 函数高效插入
myMap.emplace("cherry", 3);
1
2
3
4
5
6
7
8

2.4访问元素

可以使用键来访问对应的值：

std::cout << "apple's value: " << myMap["apple"] << std::endl;
1

如果访问的键不存在，unordered_map 会自动创建这个键，并将其初始化为对应类型的默认值（在这个例子中，值类型为 int，因此默认值为 0）。

2.5检查元素存在

你可以使用 find 方法来检查一个键是否存在：

if (myMap.find("banana") != myMap.end()) {
    std::cout << "Found banana" << std::endl;
} else {
    std::cout << "Banana not found" << std::endl;
}
1
2
3
4
5

2.6删除元素

可以使用 erase 方法来删除元素：

myMap.erase("cherry");
1

2.7遍历 unordered_map

可以使用迭代器来遍历 unordered_map 中的所有元素：

for (const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}
1
2
3

这里，pair.first 是键，pair.second 是对应的值。

2.8大小

获取 unordered_map 中元素的数量：

std::cout << "The unordered_map contains " << myMap.size() << " elements." << std::endl;
1

这些是 unordered_map 的一些基本用法。由于它基于哈希表实现，因此在大多数情况下可以提供非常快速的查找速度。

3.Code

第一次写的

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        //哈希表 存下两个数组的和
        unordered_map<int,int> mp1,mp2;
        int n = nums1.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int cn1 = nums1[i]+nums2[j];
                if(mp1.find(cn1)!=mp1.end()){//能找到
                    mp1[cn1]++;
                }else{
                    mp1[cn1]=1;
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int cn1 = nums3[i]+nums4[j];
                if(mp2.find(cn1)!=mp2.end()){//能找到
                    mp2[cn1]++;
                }else{
                    mp2[cn1]=1;
                }
            }
        }
        //预处理完毕
        int cn = 0;
        
        for(auto it : mp1){
            if(mp2.find((-1)*(it.first))!=mp2.end()){
                cn += (it.second * mp2[(-1)*(it.first)]);
            }
        }
        return cn;

    }
};
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
37
38

看完官方解之后的优化，思路是一样的，就是vector容器的遍历写法不一样，下面的写法更简便

• vector容器的循环可以用

for(auto num : nums){}
1

• 对于map容器，如果访问的键不存在，unordered_map 会自动创建这个键，并将其初始化为对应类型的默认值（在本题中，值类型为 int，因此默认值为 0）。
  所以不需要判断map中是否存在访问的键，如果想用map来实现计数，可直接++，就像下面的代码中写的那样

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> countAB;
        for (int u: A) {
            for (int v: B) {
                ++countAB[u + v];//不用判断u+v键是否存在，直接++
            }
        }
        int ans = 0;
        for (int u: C) {
            for (int v: D) {
                if (countAB.count(-u - v)) {
                    ans += countAB[-u - v];
                }
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

383. 赎金信

Problem: 383. 赎金信

1.思路

哈希表，统计magazine中字符的个数，遍历ransomNote的字符，在循环中，使用一次字符，减去相应的字符的计数，如果计数小于0，则表示ransomNote用到了magazine中没有的字符，或者ransomNote使用的字符超出了magazine中字符的个数（题目：每个字符只能被使用一次）

2.Code

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> mp;
        for(int i = 0; i < magazine.size(); i++){
            ++mp[magazine[i]];
        }
        for(int i = 0; i < ransomNote.size();i++){
            if(--mp[ransomNote[i]] < 0){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

15三数之和【有时间再看看】

18.四数之和 【有时间再看看】