代码随想录算法训练营第五天|LeetCode242，349，202，1

LeetCode 242 有效的字母异位词

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

//开了两个哈希数组，两个哈希数组进行比较
class Solution {
public:
    bool isAnagram(string s, string t) {
        //用数组做一个映射
        int res_hash1[26] = {0};
        int res_hash2[26] = {0};
        //遍历s字符串，记录s字符串中字母出现的次数
        for(int i = 0; i < s.size(); i++){
            res_hash1[s[i] - 'a']++;
        }
        //遍历t字符串，记录t字符串中字母出现的次数
        for(int i = 0; i < t.size(); i++){
            res_hash2[t[i] - 'a']++;
        }
        //两个数组进行比较
        for(int i = 0; i < 26; i++){
            if(res_hash1[i] != res_hash2[i]){
                return false;
            }
        }
        return true;
    }
};

视频讲解链接：https://www.bilibili.com/video/BV1YG411p7BA/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0242.有效的字母异位词.html

//时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。
class Solution {
public:
    bool isAnagram(string s, string t) {
        //用一个哈希数组做映射
        int res_hash[26] = {0};
        //遍历字符串s
        for(int i = 0; i < s.size(); i++){
            res_hash[s[i] - 'a']++;
        }
        //遍历字符串t
        for(int i = 0; i < t.size(); i++){
            res_hash[t[i] - 'a']--;
        }
        //可以看到，比起之前，只开辟了一个数组的空间
        for(int i = 0; i < 26; i++){
            if(res_hash[i] != 0){
                return false;
            }
        }
        return true;
    }
};

LeetCode 349 两个数组的交集

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

//使用set
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //根据题目，输出结果中的每个元素一定是唯一的
        //用set存储数组
        set<int>res1(nums1.begin(), nums1.end()); 
        set<int>res2(nums2.begin(), nums2.end());
        //新建一个数组存储交集
        vector<int>intersection;
        for(auto &elem : res2){
            if(res1.find(elem) != res1.end()){
                intersection.push_back(elem);
            }
        }
        return intersection;

    }
};

视频讲解链接：https://www.bilibili.com/video/BV1ba411S7wu/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0349.两个数组的交集.html

//使用unordered_set无序关联式容器，查询的时间复杂度为O(1)
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //可以使用unordered_set无序关联式容器，查询的时间复杂度为O(1)
        unordered_set<int> res(nums1.begin(), nums1.end());
        //创建一个unordered_set存放去重的交集结果
        unordered_set<int> results;
        //遍历
        for(auto &elem : nums2){
            if(res.find(elem) != res.end()){
                results.insert(elem);
            }
        }
        return vector<int>(results.begin(), results.end());

    }
};

LeetCode 202 快乐数

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

//利用unordered_set的特性，如果出现重复的平方和就可以返回false
class Solution {
public:
    //计算数字的每位平方之和
    int sum(int n){
	    int sum = 0;
	    while(n){
		    sum += (n % 10) * (n % 10);
		    n =  n / 10;
	    }
	    return sum;
    }

    bool isHappy(int n){
        //用unordered_set存储每次计算的平方和
        unordered_set<int> res;
        while(1){
            n = sum(n);
            if(n == 1){
                return true;
            }
            //跳出无限循环
            if(res.find(n) != res.end()){
                return false;
            }else{
                res.insert(n);
            }
                
        }
	
    }
};

视频讲解链接：无

文章讲解链接：https://programmercarl.com/0202.快乐数.html

LeetCode 1 两数之和

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

//使用map
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //找出和为目标值target的两个整数
        //设置一个map存储元素值和下标
        map<int, int> judge;
        //遍历nums数组
        for(int i = 0; i < nums.size(); i++){
            auto iter = judge.find(target - nums[i]);
            if(iter != judge.end()){
                return vector<int>{iter->second, i};
            }
            else{
                judge.insert(pair<int, int>(nums[i], i));
            }
        }
        return{};
        
    }
};

视频讲解链接：https://www.bilibili.com/video/BV1aT41177mK/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0001.两数之和.html