代码随想录算法训练营第六天 | 242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

242. 有效的字母异位词

题目链接：242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

文章讲解/视频讲解：https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

思路

用哈希表来解决，因为题目中已经提到s和t仅包含小写字母，所以哈希表可以用一个长为26的数组代替。

首先预判断，如果s和t长度不一，返回false。

设置两个哈希表，分别记录s和t中每个字母的出现次数，如果出现次数完全相同，则说明是字母异位词。

C++实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()) return false;
        vector<int> hashSet1(26, 0), hashSet2(26, 0);
        
        for(int i = 0;i<s.size();i++){
            hashSet1[s[i] - 'a'] += 1;
            hashSet2[t[i] - 'a'] += 1;
        }

        for(int i = 0;i<26;i++){
            if(hashSet1[i] != hashSet2[i]) return false;
        }
        return true;
    }
};

349. 两个数组的交集

题目链接：19.删除链表的倒数第N个节点

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

思路

用哈希表来解决，首先定义一个哈希表hashSet1，用来统计nums1中的所有元素，然后遍历nums2，如果nums2中的元素已经存在于hashSet1，则说明这个元素是两个数组的交集。这时将这个元素存入另一个哈希表hashSet2，用以去重，最后把hashSet2中的元素全都送入一个vector数组中，作为结果。

C++实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> hashSet1;
        for(int i = 0;i<nums1.size();i++){
            hashSet1.insert(nums1[i]);
        }

        unordered_set<int> hashSet2;
        
        for(int i = 0;i<nums2.size();i++){
            if(hashSet1.find(nums2[i]) != hashSet1.end()){
                hashSet2.insert(nums2[i]);
            }
        }
        vector<int> results;

        for(auto x : hashSet2){
            results.push_back(x);
        }
        return results;
    }
};

202. 快乐数

题目链接：202. 快乐数

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

「快乐数」 定义为：

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

文章讲解/视频讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

思路

同样采用哈希表的思路，定义一个函数func来计算每一个正整数所有位置的平方和。每一次循环，将当前数字curr_num送入func，计算得出一个新的值来代替curr_num，同时，将该结果存储进哈希表中，然后循环这一过程。如果当前计算得出的值为1或者已经在哈希表中，则终止。如果最终curr_num等于1，则说明是快乐数，否则不是。

C++实现

class Solution {
public:

    int calculate_square(int n){
        int result = 0;
        while(n != 0){
            int curr = n % 10;
            result += curr * curr;
            n /= 10;
        }
        return result;
    }

    bool isHappy(int n) {
        unordered_set<int> hashSet;
        int curr_num = n;
        hashSet.insert(curr_num);
        while(curr_num != 1){
            curr_num = calculate_square(curr_num);
            if(hashSet.find(curr_num) != hashSet.end()) break;
            hashSet.insert(curr_num);
        }

        return curr_num == 1;
    }
};

1. 两数之和

题目链接：1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

文章讲解/视频讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

思路

这道题是leetcode的第一道题，有很多种实现方式。我能想到的有三种，第一种方法是暴力搜索，两层循环进行遍历，这种方法的时间复杂度为o(n^2)；第二种方法是采用哈希表，首先将当前数组全部存入哈希表中，然后再对该数组进行遍历，对于数组中的每一个元素num，判断哈希表中是否有target-num这个元素，如果有，则说明我们找到了这一对元素；第三种方法是采用双指针，首先对数组进行排序，然后定义两个指针left和right，分别指向数组的头和尾，如果nums[left] + nums[right] < target，就令left++，如果nums[left] + nums[right] > target，就令right–，直到找到这一对值，不过需要注意的是，题目要求返回原数组的下标，这一点在排序时需要记录。

C++实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashMap;

        for(int i = 0;i<nums.size();i++){
            hashMap[nums[i]] = i;
        }

        vector<int> result;
        for(int i = 0;i<nums.size();i++){
            if(hashMap.find(target - nums[i]) != hashMap.end() && hashMap[target - nums[i]] != i){
                result.push_back(i);
                result.push_back(hashMap[target - nums[i]]);
                break;
            }
        }

        return result;
    }
};