【LeetCode】HOT 100（23）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】HOT 100（23）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：448. 找到所有数组中消失的数字 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：438. 找到字符串中所有字母异位词 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：448. 找到所有数组中消失的数字 - 力扣（Leetcode）

【LeetCode】HOT 100（23）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {

    }
};

解题思路：

这道题直接做的话并不难，

直接把这个数组存进哈希，然后再遍历，

看看有那个数字不在这个数组里面，push进要返回的数组就行：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        set<int> st;
        vector<int> v;
        for(auto e : nums) st.insert(e);
        for(int i = 1; i <= nums.size(); i++) {
            if(st.find(i) == st.end()) v.push_back(i);
        }
        return v;
    }
};

但是这段代码因为用的是set，

所以并不是O(N)的时间复杂度，空间复杂度也是O(N)，

题目有个进阶要求，

毕竟是简单题，我就去做了一下进阶，

如果想要达成进阶的要求，有一个很妙的解法：

思路如下：

第一遍遍历的时候，标记数组中有数字的位置，

打个比方就是，遍历到1，就把数组第一个位置标记，代表有这个数字，

如果遍历到7，就把数组第7个位置标记，代表有7这个数字，

这样子我们就知道哪些位置没有被标记。

第二次遍历数组，将没有标记的位置的数字存进数组并返回即可

代码如下：

代码：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            nums[(nums[i] - 1) % n] += n;
        }
        vector<int> v;
        for(int i = 0; i < n; i++) {
            if(nums[i] <= n) v.push_back(i + 1); 
        }
        return v;
    }
};

过过过过啦！！！！

【LeetCode】HOT 100（23）,LeetCode HOT 100,leetcode,算法,c++

题目：438. 找到字符串中所有字母异位词 - 力扣（Leetcode）

【LeetCode】HOT 100（23）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {

    }
};

解题思路：

这道题是一道经典的滑动窗口题目，

滑动窗口的题目解题的思路基本上大同小异，

就是更新右边界，然后找到符合条件的子集之后，

计数或者是将题目要求的内容输入到数组里面之类的操作，

然后移动左边界，最后遍历完就可以返回了。

代码如下：

代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, window;
        for(auto e : p) need[e]++;
        int left = 0, right = 0, cnt = 0;
        vector<int> ans;
        while(right < s.size()) {
            char r = s[right];
            right++;
            if(need.count(r) > 0) {
                window[r]++;
                if(window[r] == need[r]) {
                    cnt++;
                }
            }
            if(cnt == need.size()) ans.push_back(left);
            while(right - left >= p.size()) {
                char l = s[left];
                left++;
                if(need.count(l) > 0) {
                    if(window[l] == need[l]) {
                        cnt--;
                    }
                    window[l]--;
                }
            }
        }
        return ans;
    }
};