哈希表

题目中提到元素是否出现,考虑用哈希表进行查找。

242. 有效的字母异位词

用数组维护一个记录,t中++,s中--,最后判断数组的每一项是否为零

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};

        for(char ss : s) {
            record[ss-'a']++;
        }
        for(char tt : t) {
            record[tt-'a']--;
        }

        // 判断是否都是0
        for(int i : record) {
            if(i!=0) return false;
        }
        return true;
    }
};

349. 两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res;  //存放结果
        unordered_set<int> nums1_set(nums1.begin(),nums1.end());
        for(int v : nums2) {
            // 找到,就加入
            if(nums1_set.find(v)!=nums1_set.end()) {
                res.insert(v);
            }
        }
        return vector<int>(res.begin(), res.end());
    }
};

202. 快乐数

class Solution {
public:
    // 求和
    int getSum(int n) {
        int sum = 0;
        while(n){
            int res = n%10;  //余数
            sum += res*res;
            n/=10;  //n变为余数
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> sum_set;

        while(true) {
            int sum = getSum(n);
            if(sum == 1) return true;
            // 找到了,就无限循环了
            if(sum_set.find(sum)!=sum_set.end()) {
                return false;
            } else {
                sum_set.insert(sum);
            }
            n = sum;  
        }
    }
};

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;  // key:数组值,value:下标
        for(int i=0; i<nums.size();i++) {
            auto it = map.find((target-nums[i]));
            if(it != map.end()) {
                // 找到了
                return {i,it->second};
            } else {
                // 没找到
                map.insert(pair<int,int>(nums[i],i));
            }
        }
        return {};
    }
};

454. 四数相加 II

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> umap;  // key:a+b的值,value:这个值出现的次数
        int count = 0;
        for(int a:nums1)
            for(int b:nums2) {
                umap[a+b] ++;
            }
        for(int c:nums3)
            for(int d:nums4) {
                if(umap.find(0-(c+d)) != umap.end()) {
                    count+=umap[0-(c+d)];
                }
            }
        return count;
    }
};

383. 赎金信

和242很像

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for(char s : magazine) {
            record[s-'a']++;
        }
        for(char s: ransomNote ) {
            record[s-'a']--;
        }
        for (int v : record) {
            if(v<0) return false;
        }
        return true;
    }
};

15. 三数之和

题目中不允许出现重复的三元组,去重原因是用哈希表不方便。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //对于数组长度<3,如果数组为null 或者数组长度小于3返回[]。
        if(nums.size()<3) return {};

        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;

        for(int i=0;i<nums.size();i++) {
            int a = nums[i];
            if(a>0) return ans;  // 大于0就结束
            if(i>0 && nums[i]==nums[i-1]) continue;  // 去重
            int left = i+1;
            int right = nums.size()-1;
            while(left<right) {
                int b = nums[left];
                int c = nums[right];
                if(a+b+c>0) {
                    // 大了
                    right--;
                } else if(a+b+c<0) {
                    // 小了
                    left++;
                } else {
                    // 相等
                    ans.push_back({a,b,c});
                    // 去重
                    while(nums[left]==b && left<right) left++;
                    while(nums[right]==c && left<right) right--;
                }
            }

        }
        return ans;
    }
};

18. 四数之和

在三数之和上面,加一个循环

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if(nums.size()<4) return {};

        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for(int k=0; k<nums.size();k++) {
            if(k>0 && nums[k]==nums[k-1]) continue;  //去重
            // 下面是三数之和的写法
            int a = nums[k];
            for(int i=k+1; i<nums.size();i++) {
                if(i>k+1 && nums[i]==nums[i-1]) continue;  //去重
                int b = nums[i];
                int left = i+1;
                int right = nums.size()-1;
                while(left<right) {
                    int c = nums[left];
                    int d = nums[right];
                    if(a+b>target-c-d) {
                        right--;
                    } else if (a+b<target-c-d) {
                        left++;
                    } else {
                        ans.push_back({a,b,c,d});
                        while(nums[left]==c && left<right) left++;
                        while(nums[right]==d && left<right) right--;
                    }
                }
            }
        }
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇