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

目录

242 有效的字母异位词

349 两个数组的交集

202 快乐数

1 两数之和

---

242 有效的字母异位词

排序

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        return t == s;
    }
};

时间复杂度O(nlogn)

空间复杂度O(logn)

哈希表?

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

时间复杂度O(n + m)

空间复杂度O(s)s = 26

349 两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int>res;
        unordered_set<int>set1,set2;
        for(auto num : nums1){
            set1.insert(num);
        }
        for(auto num : nums2){
            set2.insert(num);
        }
        for(auto num : set1){
            if(set2.count(num) > 0){
                res.push_back(num);
            }
        }
        return res;
    }
};

时间复杂度O(n + m)

空间复杂度O(n + m)

202 快乐数

?暴力

class Solution {
public:
    bool isHappy(int n) {
        for(int i = 0;i < 100;i++){
            int res;
            while(n){
                int num = n % 10;
                n /= 10;
                res += num * num;
            }
            n = res;
            res = 0;
            if(n == 1)return true;
        }
        return false;
    }
};

哈希表

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int>set;
        while(n != 1 && !set.count(n)){
            set.insert(n);
            int sum = 0;
            while(n){
                sum += (n % 10)* (n % 10);
                n /= 10;
            }
            n = sum;
        }
        if(n == 1)return true;
        return false;
    }
};

时间复杂度O(logn)

空间复杂度O(logn)?

1 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>table;
        for(int i = 0;i < nums.size();i++){
            auto iterator = table.find(target - nums[i]);
            if(iterator != table.end()){
                return {iterator->second,i};
            }
            table[nums[i]] = i;
        }
        return {};
    }
};

时间复杂度O(n)

空间复杂度O(n)?