AcWing 每日一题 & 秋招

学习平台

题目1：用户分组

题解

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        unordered_map<int, vector<int>> hash;

        for(int i = 0; i < groupSizes.size(); i ++){
            int x = groupSizes[i];
            hash[x].push_back(i);

            if(hash[x].size() == x) {
                res.push_back(hash[x]);
                hash[x].clear();
            }
        }
        return res;
    }
};

时间复杂度：O(n)，其中 n 是 groupSize的长度，需遍历一遍数组。
空间复杂度：O(n)，主要取决于哈希表。

执行用时：8 ms, 在所有 C++ 提交中击败了88.05%的用户

内存消耗：12.7 MB, 在所有 C++ 提交中击败了63.05%的用户

通过测试用例：103 / 103

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < groupSizes.length; i ++){
            int x = groupSizes[i];
            if(map.get(x) == null)
                map.put(x, new ArrayList<>());
            map.get(x).add(i);
            if(map.get(x).size() == x){
                res.add(map.get(x));
                map.put(x, null);
            }
        }
        return res;
    }
}

时间复杂度：O(n)，其中 n 是 groupSize的长度，需遍历一遍数组。
空间复杂度：O(n)，主要取决于哈希表。

执行用时：7 ms, 在所有 Java 提交中击败了42.69%的用户

内存消耗：41.8 MB, 在所有 Java 提交中击败了81.09%的用户

通过测试用例：103 / 103

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        hash = {}
        res = []
        for i in range(len(groupSizes)):
            x = groupSizes[i]
            if x not in hash:
                hash[x] = []
            hash[x].append(i)
            if len(hash[x]) == x:
                res.append(hash[x])
                hash[x] = []
        return res

时间复杂度：O(n)，其中 n 是 groupSize的长度，需遍历一遍数组。
空间复杂度：O(n)，主要取决于哈希表。

执行用时：44 ms, 在所有 Python3 提交中击败了47.85%的用户

内存消耗：15 MB, 在所有 Python3 提交中击败了64.26%的用户

通过测试用例：103 / 103

题目2：最多能完成排序的块Ⅱ

768. 最多能完成排序的块 II

思路

方法1：单调栈

对于已经分好块的数组，若块数大于 1，则可以得到以下结论：右边的块的所有数字均大于或等于左边的块的所有数字。

方法2：排序 + 哈希表

将数组进行排序，然后依次比对，若在某个区间内，该区间内未排序前的数字和排序后的数字完全相等，则为一个区间。

题解

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> stk;
        for(auto x : arr){
            int t = x;
            while(stk.size() > 0 && stk.top() > x) {
                t = max(t, stk.top()); // 求已删除的最大值
                stk.pop();
            }
            stk.push(t); // 将该区间的最右边元素入栈
        }
        return stk.size();
    }
};

时间复杂度：O(n)，其中 n 是 arr的长度，需遍历一遍数组，入栈的操作最多为n次。
空间复杂度：O(n)，栈的长度最多为n。

执行用时：12 ms, 在所有 C++ 提交中击败了57.56%的用户

内存消耗：12 MB, 在所有 C++ 提交中击败了61.94%的用户

通过测试用例：139 / 139

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stk = new Stack<>();
        for(int x : arr) {
            int t = x;
            while(stk.size() > 0 && stk.peek() > x) {  // peek栈顶元素
                t = Math.max(t, stk.peek());
                stk.pop();
            }
            stk.push(t);
        }
        return stk.size();
    }
}

时间复杂度：O(n)，其中 n 是 arr的长度，需遍历一遍数组，入栈的操作最多为n次。
空间复杂度：O(n)，栈的长度最多为n。

执行用时：9 ms, 在所有 Java 提交中击败了10.83%的用户

内存消耗：41 MB, 在所有 Java 提交中击败了87.61%的用户

通过测试用例：139 / 139

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for x in arr:
            t = x
            while len(stk) and stk[-1] > x:
                t = max(t, stk[-1])
                stk.pop()
            stk.append(t)
        return len(stk)

时间复杂度：O(n)，其中 n 是 arr的长度，需遍历一遍数组，入栈的操作最多为n次。
空间复杂度：O(n)，栈的长度最多为n。

执行用时：40 ms, 在所有 Python3 提交中击败了91.12%的用户

内存消耗：15.2 MB, 在所有 Python3 提交中击败了62.74%的用户

通过测试用例：139 / 139

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        auto b = arr;
        sort(b.begin(), b.end());
        unordered_map<int, int> hash;

        int res = 0;
        for(int i = 0, cnt = 0; i < arr.size(); i ++){  // cnt记录哈希表中非零元素的个数
            hash[arr[i]] ++;
            if(hash[arr[i]] == 0) cnt --;
            else if(hash[arr[i]] == 1) cnt ++;
            hash[b[i]] --;
            if(hash[b[i]] == 0) cnt --;
            else if(hash[b[i]] == -1) cnt ++;
            if(!cnt) res ++;
        }
        return res;
    }
};

时间复杂度：O(n logn)，其中 n 是 arr的长度，排序需要消耗 O(nlogn)的时间复杂度，只需遍历一遍数组。
空间复杂度：O(n)，排序完的数组和哈希表均需要消耗 O(n) 的空间复杂度。

执行用时：24 ms, 在所有 C++ 提交中击败了13.58%的用户

内存消耗：13.5 MB, 在所有 C++ 提交中击败了10.45%的用户

通过测试用例：139 / 139

题目3：统计子矩阵

统计子矩阵

思路

需要求解每列的前缀和，然后控制子区间的上边界、下边界，右边界，通过右边界求解相应的左边界位置，进而求解满足要求的子区间个数。

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 510;

int n, m, k;
int s[N][N];

int main() {
    cin >> n >> m >> k;
    // 求每一列的前缀和
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            cin >> s[i][j];
            s[i][j] += s[i - 1][j];
        }
        
    ll res;
    for(int i = 1; i <= n; i ++)  // 遍历上边界
        for(int j = i; j <= n; j ++) {  // 遍历下边界
            for(int l = 1, r = 1, sum = 0; r <= m; r ++){  // 遍历左右边界
                sum += s[j][r] - s[i - 1][r]; // 求和
                while(sum > k) {
                    sum -= s[j][l] - s[i - 1][l];
                    l ++;
                }
                res += r - l + 1;
            }
        }

    cout << res << endl;  
    return 0;
}

时间复杂度：O(n ^ 3)，其中 n 是 s 的行数，需遍历三次。
空间复杂度：O(1)，没有额外空间。

执行用时：1927 ms,

内存消耗：2268 KB

通过测试用例：103 / 103

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String []args) {
        Scanner cin = new Scanner(System.in);
        
        int n = cin.nextInt(), m = cin.nextInt(), k = cin.nextInt();
        int [][]s = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i ++)
            for(int j = 1;j <= m; j ++)
                s[i][j] = cin.nextInt() + s[i - 1][j];
    
        long res = 0;
        for(int i = 1; i <= n; i ++)
            for(int j = i; j <= n; j++)
                for(int l = 1, r = 1, sum = 0; r <= m; r ++){
                    sum += s[j][r] - s[i - 1][r];
                    while(sum > k){
                        sum -= s[j][l] - s[i - 1][l];
                        l ++;
                    }
                    res += r - l + 1;
                }
                
        System.out.println(res);
    }
}

时间复杂度：O(n ^ 3)，其中 n 是 s 的行数，需遍历三次。
空间复杂度：O(1)，没有额外空间。

执行用时：4449 ms

内存消耗：45100 KB

通过测试用例：103 / 103

n, m, k = map(int, input().split()) # 处理输入，以空格划分

s = [[0 for i in range(m + 1)]] # 第一行全为 0 

for i in range(1, n + 1):
    s.append([0] + list(map(int, input().split())))  # 每行的第一列都是 0
    for j in range(1, m + 1):
        s[i][j] += s[i - 1][j]

res = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        l = 1
        sum = 0
        for r in range(1, m + 1):
            sum += s[j][r] - s[i - 1][r]
            while sum > k:
                sum -= s[j][l] - s[i - 1][l]
                l += 1
            res += r - l + 1

print(res)

时间复杂度：O(n ^ 3)，其中 n 是 s 的行数，需遍历三次。
空间复杂度：O(1)，没有额外空间。

执行用时：5429 ms

内存消耗：40128 KB

通过测试用例：103 / 103

题目4：设计双端队列⭐

设计循环双端队列

思路

使用长度为k + 1的数组来模拟循环队列，额外多用一个空间。

front：队头指针，直接指向对头元素，
rear：队尾指针，指向队尾元素的下一位置。
判断对空：front == rear 则队空
判断队满：rear - front == k 则队满

题解

class MyCircularDeque {
public:
    vector<int> q;
    int hh = 0, tt = 0;

    MyCircularDeque(int k) {
        q.resize(k + 1); // 设置数组的长度
    }

    int get(int x) {  // 将x重新设置为 hh~tt内的值
        return (x + q.size()) % q.size();
    }
    
    bool insertFront(int value) {
        if(isFull()) return false;
        hh = get(hh - 1);
        q[hh] = value;
        return true;
    }
    
    bool insertLast(int value) {
        if(isFull()) return false;
        q[tt] = value;
        tt = get(tt + 1);
        return true;
    }
    
    bool deleteFront() {
        if(isEmpty()) return false;
        hh = get(hh + 1);
        return true;
    }
    
    bool deleteLast() {
        if(isEmpty()) return false;
        tt = get(tt - 1);
        return true;
    }
    
    int getFront() {
        if(isEmpty()) return -1;
        return q[hh];
    }
    
    int getRear() {
        if(isEmpty()) return -1;
        return q[get(tt - 1)];
    }
    
    bool isEmpty() {
        return tt == hh;
    }
    
    bool isFull() {
        return tt == get(hh - 1);
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

时间复杂度：O(1)，初始化和每项操作的时间复杂度均为 O(1)。
空间复杂度：O(k)，其中 k 为给定的队列元素数目。

执行用时：28 ms, 在所有 C++ 提交中击败了41.89%的用户

内存消耗：16.3 MB, 在所有 C++ 提交中击败了67.79%的用户

通过测试用例：51 / 51

class MyCircularDeque {
    int []q;
    int hh = 0, tt = 0;
    public MyCircularDeque(int k) {
        q = new int[k + 1];
    }

    public int get(int x) {
        return (x + q.length) % q.length;
    }
    
    public boolean insertFront(int value) {
        if(isFull()) return false;
        hh = get(hh - 1);
        q[hh] = value;
        return true;
    }
    
    public boolean insertLast(int value) {
        if(isFull()) return false;
        q[tt] = value;
        tt = get(tt + 1);
        return true;
    }
    
    public boolean deleteFront() {
        if(isEmpty()) return false;
        hh = get(hh + 1);
        return true;
    }
    
    public boolean deleteLast() {
        if(isEmpty()) return false;
        tt = get(tt - 1);
        return true;
    }
    
    public int getFront() {
        if(isEmpty()) return -1;
        return q[hh];
    }
    
    public int getRear() {
        if(isEmpty()) return -1;
        return q[get(tt - 1)];
    }
    
    public boolean isEmpty() {
        return tt == hh;
    }
    
    public boolean isFull() {
        return tt == get(hh - 1);
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

时间复杂度：O(1)，初始化和每项操作的时间复杂度均为 O(1)。
空间复杂度：O(k)，其中 k 为给定的队列元素数目。

执行用时：4 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：42.2 MB, 在所有 Java 提交中击败了19.97%的用户

通过测试用例：51 / 51

class MyCircularDeque:

    def __init__(self, k: int):
        self.q = [0 for i in range(k + 1)]
        self.hh = 0
        self.tt = 0

    def get(self, x) -> int:
        return (x + len(self.q)) % len(self.q)

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.hh = self.get(self.hh - 1)
        self.q[self.hh] = value
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.q[self.tt] = value
        self.tt = self.get(self.tt + 1)
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.hh = self.get(self.hh + 1)
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.tt = self.get(self.tt - 1)
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[self.hh]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[self.get(self.tt - 1)]

    def isEmpty(self) -> bool:
        return self.hh == self.tt

    def isFull(self) -> bool:
        return self.tt == self.get(self.hh - 1)


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

时间复杂度：O(1)，初始化和每项操作的时间复杂度均为 O(1)。
空间复杂度：O(k)，其中 k 为给定的队列元素数目。

执行用时：68 ms, 在所有 Python3 提交中击败了89.03%的用户

内存消耗：15.7 MB, 在所有 Python3 提交中击败了45.89%的用户

通过测试用例：51 / 51

题目5：设计有序流

设计有序流

思路

题解

class OrderedStream {
public:
    vector<string> strs;
    int k = 0;

    OrderedStream(int n) {
        strs.resize(n);
    }

    vector<string> insert(int idKey, string value) {
        strs[idKey - 1] = value;
        vector<string> res;
        while (k < strs.size() && strs[k].size())
            res.push_back(strs[k ++ ]);
        return res;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */

时间复杂度：O(n)
空间复杂度：O(n)，即为存储 n 个字符串需要的空间。

执行用时：80 ms, 在所有 C++ 提交中击败了98.95%的用户

内存消耗：81.6 MB, 在所有 C++ 提交中击败了66.25%的用户

通过测试用例：101 / 101

class OrderedStream {
    String []strs;
    int k = 0;
    public OrderedStream(int n) {
        strs = new String[n];
    }
    
    public List<String> insert(int idKey, String value) {
        strs[idKey - 1] = value;
        List<String> res = new ArrayList<>();
        while(k < strs.length && strs[k] != null)
            res.add(strs[k ++]);
        return res;
    }
}

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream obj = new OrderedStream(n);
 * List<String> param_1 = obj.insert(idKey,value);
 */

时间复杂度：O(n)
空间复杂度：O(n)，即为存储 n 个字符串需要的空间。

执行用时：74 ms, 在所有 Java 提交中击败了57.69%的用户

内存消耗：42 MB, 在所有 Java 提交中击败了99.79%的用户

通过测试用例：101 / 101

class OrderedStream:

    def __init__(self, n: int):
        self.strs = ["" for i in range(n)]
        self.k = 0


    def insert(self, idKey: int, value: str) -> List[str]:
        self.strs[idKey - 1] = value
        res = []
        while self.k < len(self.strs) and self.strs[self.k] != "":
            res.append(self.strs[self.k])
            self.k += 1
        return res 


# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

时间复杂度：O(n)
空间复杂度：O(n)，即为存储 n 个字符串需要的空间。

执行用时：148 ms, 在所有 Python3 提交中击败了33.21%的用户

内存消耗：15.6 MB, 在所有 Python3 提交中击败了82.20%的用户

通过测试用例：101 / 101

题目6：层数最深叶子节点的和

层数最深叶子节点的和

思路

深度优先搜索遍历二叉树，遍历的时候维护层数：

若当前层数和目前最大层数相同，则结果加上该节点的值
若当前层数大于目前最大层数，则结果清零，并且层数重置为当前层数。

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int max = -1; // 记录最大的深度
    int sum = 0;

    void dfs(TreeNode* root, int deep) {
        if(root == nullptr) {
            return ;
        }
        if(max < deep) {
            max = deep;
            sum = root->val;
        }
        else if(max == deep){
            sum += root->val;
        }
        dfs(root->left, deep + 1);
        dfs(root->right, deep + 1);
    }

    int deepestLeavesSum(TreeNode* root) {
        dfs(root, 0);
        return sum;
    }
};

时间复杂度：O(n)，其中 n 是二叉树的节点数。深度优先搜索需要遍历每个节点一次。
空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度主要取决于递归调用栈的深度，为二叉树的深度，最坏情况下二叉树的深度是 O(n*)。

执行用时：92 ms, 在所有 C++ 提交中击败了50.95%的用户

内存消耗：58.4 MB, 在所有 C++ 提交中击败了69.41%的用户

通过测试用例：39 / 39

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int max = -1;
    int sum = 0;
    public void dfs(TreeNode root, int deep) {
        if(root == null) {
            return ;
        }
        if(max < deep) {
            max = deep;
            sum = root.val;
        } else if( max == deep){
            sum += root.val;
        }
        dfs(root.left, deep + 1);
        dfs(root.right, deep + 1);
    }
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return sum;
    }
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。深度优先搜索需要遍历每个节点一次。
空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度主要取决于递归调用栈的深度，为二叉树的深度，最坏情况下二叉树的深度是 O(n*)。

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：43.8 MB, 在所有 Java 提交中击败了60.33%的用户

通过测试用例：39 / 39

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        depth, sum = -1, 0
        def dfs(root, d):
            if not root:
                return
            nonlocal depth, sum
            if d > depth:
                depth = d
                sum = root.val
            elif d == depth:
                sum += root.val
            dfs(root.left, d + 1)
            dfs(root.right, d + 1)
        dfs(root, 0)
        return sum

时间复杂度：O(n)，其中 n 是二叉树的节点数。深度优先搜索需要遍历每个节点一次。
空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度主要取决于递归调用栈的深度，为二叉树的深度，最坏情况下二叉树的深度是 O(n*)。

执行用时：224 ms, 在所有 Python3 提交中击败了25.20%的用户

内存消耗：19.3 MB, 在所有 Python3 提交中击败了64.49%的用户

通过测试用例：39 / 39

题目7：最大相等频率

最大相等频率

思路

使用两个哈希表

第一个哈希表cnt记录对应的数在数组中出现的次数（高度）
第二个哈希表hash记录某个次数（高度）出现的次数。

分情况讨论：

若总共只有一种高度，有两种情况
- 这个高度对应的次数只有一种 hash.second == 1
- 这个高度为1 hash.first == 1
若总共只有两种高度，有两种情况
- 较小的高度为1，并且只有一次 hash[0].first == 1 && hash[0].second == 1
- 较大的高度是较小的高度 + 1，并且较大的高度只有一个 hash[1].first == hash[0].first + 1 && hash[1].second == 1
若高度有三种，则不存在解题方法。

题解

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        unordered_map<int, int> cnt, hash; // cnt记录x出现的次数（高度）， hash记录某个次数（高度）出现的个数（次数）
        int res = 0, len = 0;

        for(auto x : nums) {
            if(cnt.count(x)) {  // cnt已经加过x了
                hash[cnt[x]] --;  // 将之前的cnt[x] 次数减一
                if(!hash[cnt[x]]) hash.erase(cnt[x]); // 如果减一之后变为0了，则将cnt[x]从hash中删除
            }
            cnt[x] ++;
            hash[cnt[x]] ++;
            len ++;

            if(hash.size() == 1) {
                auto it = hash.begin();
                if(it->first == 1 || it->second == 1) // 如果所有柱子的高度等于1 或者 高度不唯一，但只有一个柱子
                    res = len; 
            } else if(hash.size() == 2) {
                vector<pair<int, int>> tmp(hash.begin(), hash.end());
                if(tmp[0].first > tmp[1].first) swap(tmp[0], tmp[1]);  // 如果第一个数比第二个数大，则交换
                if(tmp[0].first == 1 && tmp[0].second == 1) res = len;  // 较小的数只有一个并且高度为1 
                if(tmp[1].first == tmp[0].first + 1 && tmp[1].second == 1) res = len;  // 较大的数的高度是较小数的高度 + 1，并且较大的数只有一个
            }
        }
        return res;
    }
};

时间复杂度：O(n)，其中 n 是数组中元素的个数，遍历一遍数组。
空间复杂度：O(n)，两个哈希表需要 O(n) 个空间。

执行用时：232 ms, 在所有 C++ 提交中击败了9.34%的用户

内存消耗：64.1 MB, 在所有 C++ 提交中击败了12.05%的用户

通过测试用例：45 / 45

class Solution {
    public int maxEqualFreq(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>(), hash = new HashMap<>();
        int res = 0, len = 0;
        for(int x : nums) {
            Integer c = cnt.get(x);
            if(c != null) {
                hash.put(c, hash.get(c) - 1);
                if(hash.get(c) == 0)  hash.remove(c);
            }

            cnt.put(x, cnt.getOrDefault(x, 0) + 1); // cnt[x] ++;
            hash.put(cnt.get(x), hash.getOrDefault(cnt.get(x), 0) + 1);  // hash[cnt[x]] ++;
            len ++;

            if(hash.size() == 1) {
                for(Map.Entry<Integer, Integer> entry : hash.entrySet()) {
                    if(entry.getKey() == 1 || entry.getValue() == 1)
                        res = len;
                }
            } else if (hash.size() == 2) {
                int [][]tmp = new int[2][2];
                int k = 0;
                for(Map.Entry<Integer, Integer> entry : hash.entrySet()) {
                    tmp[k][0] = entry.getKey();
                    tmp[k][1] = entry.getValue();
                    k ++;
                }
                if(tmp[0][0] > tmp[1][0]) {
                    int t = tmp[0][0];
                    tmp[0][0] = tmp[1][0];
                    tmp[1][0] = t;
                    t = tmp[0][1];
                    tmp[0][1] = tmp[1][1];
                    tmp[1][1] = t;
                }
                if(tmp[0][0] == 1 && tmp[0][1] == 1) res = len;
                if(tmp[1][0] == tmp[0][0] + 1 && tmp[1][1] == 1) res = len;
            }
        }
        return res;
    }
}

时间复杂度：O(n)，其中 n 是数组中元素的个数，遍历一遍数组。
空间复杂度：O(n)，两个哈希表需要 O(n) 个空间。

执行用时：107 ms, 在所有 Java 提交中击败了7.61%的用户

内存消耗：50.4 MB, 在所有 Java 提交中击败了63.29%的用户

通过测试用例：45 / 45

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt, hash = {}, {}
        res = length = 0
        for x in nums:
            if x in cnt:
                hash[cnt[x]] -= 1
                if hash[cnt[x]] == 0:
                    del hash[cnt[x]]
            cnt[x] = cnt.get(x, 0) + 1
            hash[cnt[x]] = hash.get(cnt[x], 0) + 1
            length += 1

            if len(hash) == 1:
                items = list(hash.items())
                if items[0][0] == 1 or items[0][1] == 1:
                    res = length
            elif len(hash) == 2:
                items = list(hash.items())
                if items[0][0] > items[1][0]:
                    items[0], items[1] = items[1], items[0]
                if items[0][0] == 1 and items[0][1] == 1:
                    res = length
                if items[1][0] == items[0][0] + 1 and items[1][1] == 1:
                    res = length
        return res

时间复杂度：O(n)，其中 n 是数组中元素的个数，遍历一遍数组。
空间复杂度：O(n)，两个哈希表需要 O(n) 个空间。

执行用时：312 ms, 在所有 Python3 提交中击败了68.11%的用户

内存消耗：19.7 MB, 在所有 Python3 提交中击败了60.35%的用户

通过测试用例：45 / 45

题目8：在既定时间做作业的学生人数

在既定时间做作业的学生人数

题解

class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int res = 0;
        for(int i = 0; i < startTime.size(); i ++) {
            if(startTime[i] <= queryTime && endTime[i] >= queryTime)
                res ++;
        }
        return res;
    }
};

时间复杂度：O(n)，其中 n 是数组中元素的个数，遍历一遍数组。
空间复杂度：O(1)

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：10.5 MB, 在所有 C++ 提交中击败了71.57%的用户

通过测试用例：111 / 111

class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int res = 0;
        for(int i = 0; i < startTime.length; i ++) 
            if(startTime[i] <= queryTime && endTime[i] >= queryTime)
                res ++;
        return res;
    }
}

时间复杂度：O(n)，其中 n 是数组中元素的个数，遍历一遍数组。
空间复杂度：O(1)，

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.5 MB, 在所有 Java 提交中击败了64.01%的用户

通过测试用例：111 / 111

class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        res = 0
        for i in range(0, len(startTime)):
            if startTime[i] <= queryTime and endTime[i] >= queryTime:
                res += 1
        return res

时间复杂度：O(n)，其中 n 是数组中元素的个数，遍历一遍数组。
空间复杂度：O(1)

执行用时：36 ms, 在所有 Python3 提交中击败了72.68%的用户

内存消耗：15.1 MB, 在所有 Python3 提交中击败了5.22%的用户

通过测试用例：111 / 111

题目9：最大二叉树

最大二叉树

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(vector<int> nums, int left, int right){
        if(left >= right) return nullptr;
        int flag = -1;
        int max = -1;
        for(int i = left; i < right; i ++) {
            if(nums[i] > max) {
                max = nums[i];
                flag = i;
            }
        }
        TreeNode* node = new TreeNode(max);
        node->left = dfs(nums, left, flag);
        node->right = dfs(nums, flag + 1, right);
        return node;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(nums, 0, nums.size());
    }
};

时间复杂度：*O(n^2)，其中 n 是数组 nums 的长度。在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i 0 =< i <= n 层需要遍历 n − i 个元素以找出最大值，总时间复杂度为 O(n^2)。
空间复杂度：O(n)，即为最坏情况下需要使用的栈空间。

执行用时：196 ms, 在所有 C++ 提交中击败了5.40%的用户

内存消耗：370.8 MB, 在所有 C++ 提交中击败了5.00%的用户

通过测试用例：107 / 107

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode dfs(int[] nums, int l, int r) {
        if(l >= r) return null;
        int max = -1;
        int npc = -1;
        for(int i = l; i < r; i ++) {
            if(max < nums[i]){
                max = nums[i];
                npc = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = dfs(nums, l, npc);
        root.right = dfs(nums, npc + 1, r);
        return root;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length);
        
    }
}

时间复杂度：*O(n^2)，其中 n 是数组 nums 的长度。在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i 0 =< i <= n 层需要遍历 n − i 个元素以找出最大值，总时间复杂度为 O(n^2)。
空间复杂度：O(n)，即为最坏情况下需要使用的栈空间。

执行用时：2 ms, 在所有 Java 提交中击败了83.20%的用户

内存消耗：41.3 MB, 在所有 Java 提交中击败了84.77%的用户

通过测试用例：107 / 107

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(nums, l, r):
            if l >= r:
                return 
            max = npc = -1
            for i in range(l, r):
                if nums[i] > max:
                    max = nums[i]
                    npc = i
            node = TreeNode(max)
            node.left = dfs(nums, l, npc)
            node.right = dfs(nums, npc + 1, r)
            return node
        return dfs(nums, 0, len(nums))

时间复杂度：*O(n^2)，其中 n 是数组 nums 的长度。在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i 0 =< i <= n 层需要遍历 n − i 个元素以找出最大值，总时间复杂度为 O(n^2)。
空间复杂度：O(n)，即为最坏情况下需要使用的栈空间。

执行用时：112 ms, 在所有 Python3 提交中击败了75.67%的用户

内存消耗：15.5 MB, 在所有 Python3 提交中击败了69.26%的用户

通过测试用例：107 / 107

题目10：将矩阵按对角线排序⭐

将矩阵按对角线排序

思路

首先遍历截距，每条对角线对应到坐标系都会存在一个截距，首先根据截距确定对角线，然后根据 x 值确定 y ，进而将对角线元素加入到一个临时数组中并进行排序后又重新赋值会原数组。

题解

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();  // 行，列
        for(int b = -(n - 1); b <= m - 1; b ++) {  // 遍历截距
            vector<int> res;
            for(int x = 0, y = b; x < n && y < m; x ++, y ++) 
                if(y >= 0)
                    res.push_back(mat[x][y]);
            sort(res.begin(), res.end());
            for(int x = 0, y = b, k = 0; x < n && y < m; x ++, y ++)
                if(y >= 0)
                    mat[x][y] = res[k ++];
        }
        return mat;
    }
};

时间复杂度：O((m+n) × min(m,n) × log(min(m,n)))
空间复杂度：O(n + m)。

执行用时：8 ms, 在所有 C++ 提交中击败了85.51%的用户

内存消耗：9.1 MB, 在所有 C++ 提交中击败了38.16%的用户

通过测试用例：15 / 15

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        for(int b = -(n - 1); b <= m - 1; b ++) {
            ArrayList<Integer> q = new ArrayList<>();
            for(int x = 0, y = b; x < n && y < m; x ++, y ++)
                if(y >= 0)
                    q.add(mat[x][y]);
            q.sort(Comparator.naturalOrder());
            for(int x = 0, y = b, k = 0; x < n && y < m; x ++, y ++) {
                if(y >= 0)
                    mat[x][y] = q.get(k ++);
            }
        }
        return mat;
    }
}

时间复杂度：O((m+n) × min(m,n) × log(min(m,n)))
空间复杂度：O(n + m)。

执行用时：7 ms, 在所有 Java 提交中击败了39.29%的用户

内存消耗：42.5 MB, 在所有 Java 提交中击败了61.04%的用户

通过测试用例：15 / 15

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        n, m = len(mat), len(mat[0])
        for b in range(-(n -1), m):
            res = []
            x, y = 0, b
            while x < n and y < m:
                if y >= 0:
                    res.append(mat[x][y])
                x += 1
                y += 1
            res.sort()
            x, y, k = 0, b, 0
            while x < n and y < m:
                if y >= 0:
                    mat[x][y] = res[k]
                    k += 1
                x += 1
                y += 1
        return mat

时间复杂度：O((m+n) × min(m,n) × log(min(m,n)))
空间复杂度：O(n + m)。

执行用时：48 ms, 在所有 Python3 提交中击败了58.73%的用户

内存消耗：15.2 MB, 在所有 Python3 提交中击败了80.95%的用户

通过测试用例：15 / 15

题目11：逃离迷宫⭐

逃离迷宫

思路

题解

题目12：将数字变成0的操作次数

将数字变成 0 的操作次数

题解

class Solution {
public:
    int numberOfSteps(int num) {
        int res = 0;
        while(num){
            res ++;
            if(num % 2 == 0)
                num /= 2;
            else 
                num --;
        }
        return res;
    }
};

时间复杂度：O(log num)，其中 num 是输入数值。每次循环都将 num 的数值减半，因此时间复杂度为 O(log num)。
空间复杂度：O(1)。只需要常数空间。

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：5.8 MB, 在所有 C++ 提交中击败了51.49%的用户

通过测试用例：204 / 204

class Solution {
    public int numberOfSteps(int num) {
        int res = 0;
        while(num != 0) {
            res ++;
            if(num % 2 == 0)
                num /= 2;
            else 
                num --;
        }
        return res;
    }
}

时间复杂度：O(log num)，其中 num 是输入数值。每次循环都将 num 的数值减半，因此时间复杂度为 O(log num)。
空间复杂度：O(1)。只需要常数空间。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.5 MB, 在所有 Java 提交中击败了41.23%的用户

通过测试用例：204 / 204

class Solution:
    def numberOfSteps(self, num: int) -> int:
        res = 0
        while num != 0:
            res += 1
            if num % 2 == 0:
                num /= 2
            else:
                num -= 1
        return res

时间复杂度：O(log num)，其中 num 是输入数值。每次循环都将 num 的数值减半，因此时间复杂度为 O(log num)。
空间复杂度：O(1)。只需要常数空间。

执行用时：32 ms, 在所有 Python3 提交中击败了90.62%的用户

内存消耗：14.9 MB, 在所有 Python3 提交中击败了59.81%的用户

通过测试用例：204 / 204

题目13：大小为 K 且平均值大于等于阈值的子数组数目

大小为 K 且平均值大于等于阈值的子数组数目

题解

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int res = 0;
        int sum = 0;
        for(int l = 0, r = 0;r < arr.size(); r ++) {
            sum += arr[r];
            if(r >= k) { // 需要删除左边元素
                sum -= arr[l ++];
            }
            if(r - l + 1 == k && sum >= threshold * k) res ++;
        }
        return res;
    }
};

时间复杂度：O(n)，其中 n 是数组长度。遍历一遍数组即可
空间复杂度：O(1)。只需要常数空间。

执行用时：64 ms, 在所有 C++ 提交中击败了81.86%的用户

内存消耗：54.1 MB, 在所有 C++ 提交中击败了16.03%的用户

通过测试用例：69 / 69

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int res = 0;
        int sum = 0;
        for (int l = 0, r = 0; r < arr.length; r ++) {
            sum += arr[r];
            if(r >= k) 
                sum -= arr[l ++];
            if(r - l + 1 == k && sum >= threshold * k) res ++;
        }
        return res;
    }
}

时间复杂度：O(n)，其中 n 是数组长度。遍历一遍数组即可
空间复杂度：O(1)。只需要常数空间。

执行用时：3 ms, 在所有 Java 提交中击败了38.01%的用户

内存消耗：52.8 MB, 在所有 Java 提交中击败了10.59%的用户

通过测试用例：69 / 69

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        res, sum = 0, 0
        l = 0
        for r in range (0, len(arr)):
            sum += arr[r]
            if r >= k:
                sum -= arr[l]
                l += 1
            if r - l + 1 == k and sum >= threshold * k:
                res += 1
        return res

时间复杂度：O(n)，其中 n 是数组长度。遍历一遍数组即可
空间复杂度：O(1)。只需要常数空间。

执行用时：148 ms, 在所有 Python3 提交中击败了37.55%的用户

内存消耗：25 MB, 在所有 Python3 提交中击败了39.74%的用户

通过测试用例：69 / 69

题目14：时钟指针的夹角

时钟指针的夹角

思路

都以 12 的位置作为 0 度，

分针的夹角：m = (double)minutes * 360 / 60
时针的夹角：h = hour % 12 * 30 + (double)minutes * 30.0 / 60.0

题解

class Solution {
public:
    double angleClock(int hour, int minutes) {
        double m = (double)minutes * 360 / 60; // 分针的度数
        double h = hour % 12 * 30 + (double)minutes * 30.0 / 60.0; // 时针的角度
        double res = abs(m - h);
        if(res > 180)   res = 360 - res;
        return res;
    }
};

时间复杂度：O(1)，
空间复杂度：O(1)。只需要常数空间。

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：5.7 MB, 在所有 C++ 提交中击败了80.22%的用户

通过测试用例：105 / 105

class Solution {
    public double angleClock(int hour, int minutes) {
        double m = (double)minutes * 360 / 60;
        double h = hour % 12 * 30 + (double) minutes * 30.0 / 60.0;
        double res = Math.abs(m - h);
        if (res > 180) res = 360 - res;
        return res;
    }
}

时间复杂度：O(1)。
空间复杂度：O(1)。只需要常数空间。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.3 MB, 在所有 Java 提交中击败了90.91%的用户

通过测试用例：105 / 105

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        m = minutes * 360 / 60
        h = hour % 12 * 30 + minutes * 30 / 60
        res = abs(m - h)
        if res > 180:
            res = 360 - res
        return res

时间复杂度：O(1)，
空间复杂度：O(1)。只需要常数空间。

执行用时：40 ms, 在所有 Python3 提交中击败了39.86%的用户

内存消耗：14.9 MB, 在所有 Python3 提交中击败了56.52%的用户

通过测试用例：105 / 105

题目15：跳跃游戏 IV⭐

跳跃游戏 IV

思路

用哈希表存储每个值对应的所有下标，然后使用bfs进行遍历

题解

class Solution {
public:
    int minJumps(vector<int>& arr) {
        if(arr.size() == 1) return 0;
        int n = arr.size(), INF = 1e9;
        if(arr[0] == arr[n - 1]) return 1;
        unordered_map<int, vector<int>> hash; // 用于存储某一个数值对应的下标编号

        for(int i = 0; i < n; i ++){
            hash[arr[i]].push_back(i);
        }

        vector<int> dist(n, INF);
        queue<int> q;
        q.push(0);
        dist[0] = 0;

        // 对头元素
        while(!q.empty()) {
            int t = q.front(); 
            q.pop();
            
            for(int i = t - 1; i <= t + 1; i += 2) {
                if(i >= 0 && i < n && dist[i] > dist[t] + 1){
                    dist[i] = dist[t] + 1;
                    q.push(i);
                }
            }

            int val = arr[t];
            if(hash.count(val)){
                for(int i : hash[val]) {
                    if(dist[i] > dist[t] + 1){
                        dist[i] = dist[t] + 1;
                        q.push(i);
                    }
                }
            }
            hash.erase(val);
        }

        return dist[n - 1];
    }
};

时间复杂度：O(n)，其中 n 是数组 arr 的长度，每个元素最多只进入队列一次，最多被判断是否需要进入队列三次。
空间复杂度：O(n)。其中 n 是数组 arr 的长度，队列，哈希表和哈希集合均最多存储 n 个元素。

执行用时：160 ms, 在所有 C++ 提交中击败了85.52%的用户

内存消耗：71.4 MB, 在所有 C++ 提交中击败了71.67%的用户

通过测试用例：33 / 33

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length, INF = 1000000;
        Map<Integer, List<Integer>> hash = new HashMap<>();
        for(int i = 0; i < n; i ++) {
            int val = arr[i];
            if(hash.get(val) == null) hash.put(val, new LinkedList<>());
            hash.get(val).add(i);
        }

        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        dist[0] = 0;

        while(!q.isEmpty()) {
            int t = q.remove(); // 返回并且删除对头元素
            for(int i = t - 1; i <= t + 1; i += 2){
                if(i >= 0 && i < n && dist[i] > dist[t] + 1){
                    dist[i] = dist[t] + 1;
                    q.add(i);
                }
            }

            int val = arr[t];
            if(hash.get(val) != null) {
                for(int i : hash.get(val)) {
                    if(dist[i] > dist[t] + 1){
                        dist[i] = dist[t] + 1;
                        q.add(i);
                    }
                }
                hash.remove(val);
            }
        }
        return dist[n - 1];
        
    }
}

时间复杂度：O(n)，其中 n 是数组 arr 的长度，每个元素最多只进入队列一次，最多被判断是否需要进入队列三次。
空间复杂度：O(n)。其中 n 是数组 arr 的长度，队列，哈希表和哈希集合均最多存储 n 个元素。

执行用时：56 ms, 在所有 Java 提交中击败了52.22%的用户

内存消耗：49.7 MB, 在所有 Java 提交中击败了97.91%的用户

通过测试用例：33 / 33

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n ,INF = len(arr), 1e8
        hash = {}
        for i in range(n):
            val = arr[i]
            if val not in hash: hash[val] = []
            hash[val].append(i)
        
        dist = [INF for i in range(n)]
        q = deque()  # 队列
        q.append(0)
        dist[0] = 0

        while q:
            t = q.popleft()
            for i in range(t - 1, t + 2):
                if i >= 0 and i < n and dist[i] > dist[t] + 1:
                    dist[i] = dist[t] + 1
                    q.append(i)
            
            val = arr[t]
            if val in hash:
                for i in hash[val]:
                    if dist[i] > dist[t] + 1:
                        dist[i] = dist[t] + 1
                        q.append(i)
                del hash[val]
        return dist[n - 1]

时间复杂度：O(n)，其中 n 是数组 arr 的长度，每个元素最多只进入队列一次，最多被判断是否需要进入队列三次。
空间复杂度：O(n)。其中 n 是数组 arr 的长度，队列，哈希表和哈希集合均最多存储 n 个元素。

执行用时：428 ms, 在所有 Python3 提交中击败了24.12%的用户

内存消耗：27.7 MB, 在所有 Python3 提交中击败了92.97%的用户

通过测试用例：33 / 33

题目16：检查整数及其两倍数是否存在

检查整数及其两倍数是否存在

思路

使用哈希表存储遍历过的元素，当当前元素的二倍或者二分之一已经在哈希表中了，则直接返回true

题解

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> hash;
        for(int x : arr){
            if(hash.count(x * 2) || x % 2 == 0 && hash.count(x / 2)) {
                return true;
            }
            hash.insert(x);
        }
        return false;
    }
};

时间复杂度：O(n)，其中 n 是数组 arr 的长度，只需要遍历一遍数组即可。
空间复杂度：O(n)。其中 n 是数组 arr 的长度，哈希表最多存 n 个元素。

执行用时：8 ms, 在所有 C++ 提交中击败了56.54%的用户

内存消耗：10.1 MB, 在所有 C++ 提交中击败了31.83%的用户

通过测试用例：107 / 107

class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> hash = new HashSet<>();
        for(int x : arr) {
            if(hash.contains(x * 2) || x % 2 == 0 && hash.contains(x / 2))
                return true;
            hash.add(x);
        }
        return false;
    }
}

时间复杂度：O(n)，其中 n 是数组 arr 的长度，只需要遍历一遍数组即可。
空间复杂度：O(n)。其中 n 是数组 arr 的长度，哈希表最多存 n 个元素。

执行用时：1 ms, 在所有 Java 提交中击败了99.56%的用户

内存消耗：40.6 MB, 在所有 Java 提交中击败了98.11%的用户

通过测试用例：107 / 107

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        hash = set()
        for x in arr:
            if x * 2 in hash or x % 2 == 0 and x / 2 in hash:
                return True
            hash.add(x)
        return False

时间复杂度：O(n)，其中 n 是数组 arr 的长度，只需要遍历一遍数组即可。
空间复杂度：O(n)。其中 n 是数组 arr 的长度，哈希表最多存 n 个元素。

执行用时：40 ms, 在所有 Python3 提交中击败了69.62%的用户

内存消耗：15.1 MB, 在所有 Python3 提交中击败了29.24%的用户

通过测试用例：107 / 107

学习平台

题目1：用户分组

标签

题解

题目2：最多能完成排序的块Ⅱ

标签

思路

题解

题目3：统计子矩阵

标签

思路

题解

题目4：设计双端队列⭐

标签

思路

题解

题目5：设计有序流

标签

思路

题解

题目6：层数最深叶子节点的和

标签

思路

题解

题目7：最大相等频率

标签

思路

题解

题目8：在既定时间做作业的学生人数

标签

题解

题目9：最大二叉树

标签

题解

题目10：将矩阵按对角线排序⭐

标签

思路

题解

题目11：逃离迷宫⭐

标签

思路

题解

题目12：将数字变成0的操作次数

标签

题解

题目13：大小为 K 且平均值大于等于阈值的子数组数目

标签

题解

题目14：时钟指针的夹角

标签

思路

题解

题目15：跳跃游戏 IV⭐

标签

思路

题解

题目16：检查整数及其两倍数是否存在

标签

思路

题解