给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

 

示例 1：

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4

 

提示：

• 1 <= events.length <= 105
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 105

方法一：按开始时间分组 + 最小堆

分析

观察一：第一天（即开始时间 $\textit{startDay}_i$ 的最小值）一定要参加会议，若不参加，岂不是白白浪费机会？比如有个会议是 $[1,1]$，不参加就错过了。

或者说，对于任意最优解，如果第一天什么也没做，我们总是可以把其中某个会议的参加时间改成第一天。

如果有多个会议的 $\textit{startDay}_i$ 都相同呢？比如有三个会议 $[1,1],[1,2],[1,3]$，参加哪个会议更好？

观察二：参加结束时间 $\textit{endDay}_i$ 最小的会议。如果第一天不参加会议 $[1,1]$，而是参加会议 $[1,2]$，那么第二天就没法参加会议 $[1,1]$ 了。

参加 $\textit{endDay}_i$ 最小的会议后，问题变成从第二天开始，解决剩余 $n-1$ 个会议的子问题。

需要知道哪些信息？

在第一天，可以参加哪些会议？

在第二天，可以参加哪些会议？

在第 $i$ 天，可以参加哪些会议？

若按照开始时间分组，那么在第 $i$ 天，开始时间为 $i$ 的会议就是新增的可以参加的会议。

此外，还需要知道在剩余可以参加的会议中，结束时间最小的会议。根据观察二，参加这个会议。

算法

把会议按照开始时间分组，用 $\textit{groups}[i]$ 表示所有开始时间为 $i$ 的会议的结束时间。

我们需要一个数据结构维护结束时间。这个数据结构需要支持如下操作：

• 添加结束时间。
• 查询结束时间的最小值。
• 删除最小的结束时间，表示我们参加这个会议，或者这个会议已过期（结束时间小于当前时间）。

最小堆完美符合要求。

在第 $i$ 天：

1. 删除最小堆中结束时间小于 $i$ 的会议（已过期）。
2. 把开始时间为 $i$ 的会议的结束时间，加到最小堆中。
3. 如果最小堆不为空，那么弹出堆顶（参加会议），把答案加一。

###py

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        mx = max(e[1] for e in events) 

        # 按照开始时间分组
        groups = [[] for _ in range(mx + 1)]
        for e in events:
            groups[e[0]].append(e[1])

        ans = 0
        h = []
        for i, g in enumerate(groups):
            # 删除过期会议
            while h and h[0] < i:
                heappop(h)
            # 新增可以参加的会议
            for end_day in g:
                heappush(h, end_day)
            # 参加一个结束时间最早的会议
            if h:
                ans += 1
                heappop(h)
        return ans

###java

class Solution {
    public int maxEvents(int[][] events) {
        int mx = 0;
        for (int[] e : events) {
            mx = Math.max(mx, e[1]);
        }

        // 按照开始时间分组
        List<Integer>[] groups = new ArrayList[mx + 1];
        Arrays.setAll(groups, i -> new ArrayList<>());
        for (int[] e : events) {
            groups[e[0]].add(e[1]);
        }

        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i <= mx; i++) {
            // 删除过期会议
            while (!pq.isEmpty() && pq.peek() < i) {
                pq.poll();
            }
            // 新增可以参加的会议
            for (int endDay : groups[i]) {
                pq.offer(endDay);
            }
            // 参加一个结束时间最早的会议
            if (!pq.isEmpty()) {
                ans++;
                pq.poll();
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int mx = 0;
        for (auto& e : events) {
            mx = max(mx, e[1]);
        }

        // 按照开始时间分组
        vector<vector<int>> groups(mx + 1);
        for (auto& e : events) {
            groups[e[0]].push_back(e[1]);
        }

        int ans = 0;
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 0; i <= mx; i++) {
            // 删除过期会议
            while (!pq.empty() && pq.top() < i) {
                pq.pop();
            }
            // 新增可以参加的会议
            for (int end_day : groups[i]) {
                pq.push(end_day);
            }
            // 参加一个结束时间最早的会议
            if (!pq.empty()) {
                ans++;
                pq.pop();
            }
        }
        return ans;
    }
};

###go

func maxEvents(events [][]int) (ans int) {
    mx := 0
    for _, e := range events {
        mx = max(mx, e[1])
    }

    // 按照开始时间分组
    groups := make([][]int, mx+1)
    for _, e := range events {
        groups[e[0]] = append(groups[e[0]], e[1])
    }

    h := &hp{}
    for i, g := range groups {
        // 删除过期会议
        for h.Len() > 0 && h.IntSlice[0] < i {
            heap.Pop(h)
        }
        // 新增可以参加的会议
        for _, endDay := range g {
            heap.Push(h, endDay)
        }
        // 参加一个结束时间最早的会议
        if h.Len() > 0 {
            ans++
            heap.Pop(h)
        }
    }
    return
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

###js

var maxEvents = function(events) {
    let mx = 0;
    for (const e of events) {
        mx = Math.max(mx, e[1]);
    }

    // 按照开始时间分组
    const groups = Array.from({ length: mx + 1 }, () => []);
    for (const [startDay, endDay] of events) {
        groups[startDay].push(endDay);
    }

    let ans = 0;
    const pq = new MinPriorityQueue();
    for (let i = 0; i <= mx; i++) {
        // 删除过期会议
        while (!pq.isEmpty() && pq.front() < i) {
            pq.dequeue();
        }
        // 新增可以参加的会议
        for (const endDay of groups[i]) {
            pq.enqueue(endDay);
        }
        // 参加一个结束时间最早的会议
        if (!pq.isEmpty()) {
            pq.dequeue();
            ans++;
        }
    }
    return ans;
};

###rust

use std::collections::BinaryHeap;

impl Solution {
    pub fn max_events(events: Vec<Vec<i32>>) -> i32 {
        let mut mx = 0;
        for e in &events {
            mx = mx.max(e[1]);
        }

        // 按照开始时间分组
        let mut groups = vec![vec![]; (mx + 1) as usize];
        for e in events {
            groups[e[0] as usize].push(e[1]);
        }

        let mut ans = 0;
        let mut h = BinaryHeap::<i32>::new();
        for (i, g) in groups.into_iter().enumerate() {
            // 删除过期会议
            while let Some(end_day) = h.peek() {
                if -end_day >= i as i32 {
                    break;
                }
                h.pop();
            }
            // 新增可以参加的会议
            for end_day in g {
                h.push(-end_day); // 取相反数，变成最小堆
            }
            // 参加一个结束时间最早的会议
            if let Some(_) = h.pop() {
                ans += 1;
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n+U\log n)$，其中 $n$ 是 $\textit{events}$ 的长度，$U=\max(\textit{endDay}_i)$。
• 空间复杂度：$\mathcal{O}(n+U)$。

方法二：按结束时间排序 + 并查集

把问题换个表述，大家就很熟悉了：

• 你有 $n$ 门课程要考试，第 $i$ 门课程可以复习的时间段为 $[\textit{startDay}_i, \textit{endDay}_i]$。对于每门课程，你可以选择时间段内的一天速通复习，一天最多复习一门课程。为了最大化可以复习的课程数，应该如何安排？

优先复习临考（$\textit{endDay}_i$ 小）的课程，即按照 $\textit{endDay}_i$ 从小到大排序。对于每门课，选择区间中最早的未被占用的那天复习。

这可以用并查集实现：

• 当 $i$ 被占用时，合并 $i$ 和 $i+1$，把 $i$ 指向 $i+1$。
• 如此一来，通过 $\text{find}(\textit{startDay}_i)$ 找到的值，就是 $\ge \textit{startDay}_i$ 的未被占用的最小值 $x$。如果 $x\le \textit{endDay}_i$，那么就可以在 $x$ 这一天复习。然后合并 $x$ 和 $x+1$，表示 $x$ 被占用。

###py

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda e: e[1])

        mx = events[-1][1]
        fa = list(range(mx + 2))

        def find(x: int) -> int:
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]

        ans = 0
        for start_day, end_day in events:
            x = find(start_day)  # 查找从 start_day 开始的第一个可用天
            if x <= end_day:
                ans += 1
                fa[x] = x + 1  # 标记 x 已占用
        return ans

###java

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        int mx = events[events.length - 1][1];
        int[] fa = new int[mx + 2];
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }

        int ans = 0;
        for (int[] e : events) {
            int x = find(e[0], fa); // 查找从 startDay 开始的第一个可用天
            if (x <= e[1]) {
                ans++;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        return ans;
    }

    private int find(int x, int[] fa) {
        if (fa[x] != x) {
            fa[x] = find(fa[x], fa);
        }
        return fa[x];
    }
}

###cpp

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        ranges::sort(events, {}, [](auto& e) { return e[1]; });

        int mx = events.back()[1];
        vector<int> fa(mx + 2);
        ranges::iota(fa, 0);

        auto find = [&](this auto&& find, int x) -> int {
            if (fa[x] != x) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        };

        int ans = 0;
        for (auto& e : events) {
            int x = find(e[0]); // 查找从 startDay 开始的第一个可用天
            if (x <= e[1]) {
                ans++;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        return ans;
    }
};

###go

func maxEvents(events [][]int) (ans int) {
    slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })

    mx := events[len(events)-1][1]
    fa := make([]int, mx+2)
    for i := range fa {
        fa[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    for _, e := range events {
        x := find(e[0]) // 查找从 startDay 开始的第一个可用天
        if x <= e[1] {
            ans++
            fa[x] = x + 1 // 标记 x 已占用
        }
    }
    return
}

###js

var maxEvents = function(events) {
    events.sort((a, b) => a[1] - b[1]);

    const mx = events[events.length - 1][1];
    const fa = _.range(mx + 2);

    function find(x) {
        if (fa[x] !== x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    let ans = 0;
    for (const [startDay, endDay] of events) {
        const x = find(startDay); // 查找从 startDay 开始的第一个可用天
        if (x <= endDay) {
            ans++;
            fa[x] = x + 1; // 标记 x 已占用
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn max_events(mut events: Vec<Vec<i32>>) -> i32 {
        events.sort_unstable_by_key(|a| a[1]);

        let mx = events.last().unwrap()[1] as usize;
        let mut fa = (0..=mx+1).collect::<Vec<_>>();

        fn find(x: usize, fa: &mut [usize]) -> usize {
            if fa[x] != x {
                fa[x] = find(fa[x], fa);
            }
            fa[x]
        }

        let mut ans = 0;
        for e in events {
            let x = find(e[0] as usize, &mut fa); // 查找从 startDay 开始的第一个可用天
            if x <= e[1] as usize {
                ans += 1;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(U + n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度，$U=\max(\textit{endDay}_i)$。
• 空间复杂度：$\mathcal{O}(U)$。

注：用哈希表实现并查集，可以做到 $\mathcal{O}(n\log n)$ 时间和 $\mathcal{O}(n)$ 空间。留给感兴趣的读者思考。

相似题目

1. 贪心题单的「二、区间贪心」。
2. 数据结构题单的「五、堆（优先队列）」。
3. 数据结构题单的「§7.4 数组上的并查集」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解题思路

        发现这么写，比较简单。。。就按照结束时间升序排序即可，然后用个set，对区间从前往后遍历，如果这个点上没安排会议就添加进去。。对于 $100000*[1,100000]$这种例子不太可行，数据水（本人菜鸡大佬们轻喷

优先队列参考这位老哥的！这是本题最好的思路！他写的非常清楚了，我就给大家引路了！

        我在这补充下我这个为什么要根据结束时间升序排序。。有的小伙伴有点模糊，假设已经安排了一些会议，我们现在再安排的会议肯定是不能和之前冲突的对吧。有这么几种选择

• 安排剩下的里面，具有最早开始时间的
• 安排剩下的里面，持续时间最短的
• 安排剩下的里面，具有最早结束时间的。

        选择第一种，极端情况是开始很早，持续时间很长，选择第二种，持续时间很短，开始很晚，选择第三种最早结束时间，可以理解为最早开始时间+持续时间也最短，所以按照最早结束时间升序排序就是这么来的。

        或者这么说，哪个会今天要结束了，我一定得去参加这个，因为别的会，改天能再参加啊，但是这个会，今天没了就没了，所以说这个会我一定要参加，才能保证参加的会最多（滑稽，我才不喜欢开会），这就是贪心。。

代码

思路一，时间复杂度 $O(n^2)$ 超时

###java

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (o1, o2) -> o1[1] - o2[1]);
        Set<Integer> set = new HashSet<>();
        for (int[] event : events) {
            int s = event[0];
            int e = event[1];
            for (int i = s; i <=e; i++) {
                if (!set.contains(i)) {
                    set.add(i);
                    break;
                }
            }
        }
        return set.size();
    }
}

###c++

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), [](const vector<int>& e1, const vector<int>& e2) {
           return e1[1] < e2[1];
        });

        unordered_set<int> res;
        for(vector<int> e: events) {
            for(int d = e[0]; d <= e[1]; d++) {
                if(res.find(d) == res.end()) {
                    res.insert(d);
                    break;
                }
            }
        }

        return res.size();
    }
};

###python

class Solution:
    def maxEvents(self,events):
        events.sort(key=lambda x:x[1])
        visited = set()
        for s,e in events:
            for day in range(s,e+1):
                if day not in visited:
                    visited.add(day)
                    break
        return len(visited)

改进版：在选择结束时间早的先分配的基础上，也要判断区间的可行性，也就是根据右端点选择区间分配，需要用到优先队列，时间复杂度 $O(nlogn)$

###java

    public int maxEvents(int[][] events) {
        //首先排序：开始时间小的在前。这样是方便我们顺序遍历，把开始时间一样的都放进堆
        Arrays.sort(events, (o1, o2) -> o1[0] - o2[0]);
        //小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //结果、开始时间、events下标、有多少组数据
        int res = 0, last = 1, i = 0, n = events.length;
        while (i < n || !pq.isEmpty()) {
            //将start相同的会议都放进堆里
            while (i < n && events[i][0] == last) {
                pq.offer(events[i++][1]);
            }
            //pop掉当前天数之前的
            while (!pq.isEmpty() && pq.peek() < last) {
                pq.poll();
            }
            //顶上的就是俺们要参加的
            if (!pq.isEmpty()) {
                pq.poll();
                res++;
            }
            last++;
        }
        return res;
    }

这是一道典型的扫描算法题。由于每个时间点最多参加一个会议，我们可以从1开始遍历所有时间。

对于每一个时间点，所有在当前时间及之前时间开始，并且在当前时间还未结束的会议都是可参加的。显然，在所有可参加的会议中，选择结束时间最早的会议是最优的，因为其他会议还有更多的机会可以去参加。

怎样动态获得当前结束时间最早的会议呢？我们可以使用一个小根堆记录所有当前可参加会议的结束时间。在每一个时间点，我们首先将当前时间点开始的会议加入小根堆，再把当前已经结束的会议移除出小根堆（因为已经无法参加了），然后从剩下的会议中选择一个结束时间最早的去参加。

为了快速获得当前时间点开始的会议，我们以$O(N)$时间预处理得到每个时间点开始的会议的序号。

算法总的时间复杂度为$O(T\log N)$（这里的$T$为时间范围）。

参考代码

###cpp

const int MAX = 1e5 + 1;

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        vector<vector<int>> left(MAX);
        for (int i = 0; i < events.size(); ++i)
            left[events[i][0]].emplace_back(i);
        
        int ans = 0;
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 1; i < MAX; ++i) {
            for (int j : left[i])
                pq.push(events[j][1]);
            while (!pq.empty() && pq.top() < i)
                pq.pop();
            if (!pq.empty()) {
                pq.pop();
                ans++;
            }
        }
        return ans;
    }
};

方法一：哈希表

我们注意到，数组 $\textit{nums1}$ 的长度不超过 ${10}^3$，数组 $\textit{nums2}$ 的长度达到 ${10}^5$，因此，如果直接暴力枚举所有下标对 $(i, j)$，计算 $\textit{nums1}[i] + \textit{nums2}[j]$ 是否等于指定值 $\textit{tot}$，那么会超出时间限制。

能否只枚举长度较短的数组 $\textit{nums1}$ 呢？答案是可以的。我们用一个哈希表 $\textit{cnt}$ 统计数组 $\textit{nums2}$ 中每个元素出现的次数，然后枚举数组 $\textit{nums1}$ 中的每个元素 $x$，计算 $\textit{cnt}[\textit{tot} - x]$ 的值之和即可。

在调用 $\text{add}$ 方法时，我们需要先将 $\textit{nums2}[index]$ 对应的值从 $\textit{cnt}$ 中减去 $1$，然后将 $\textit{nums2}[index]$ 的值加上 $\textit{val}$，最后将 $\textit{nums2}[index]$ 对应的值加上 $1$。

在调用 $\text{count}$ 方法时，我们只需要遍历数组 $\textit{nums1}$，对于每个元素 $x$，计算 $\textit{cnt}[\textit{tot} - x]$ 的值之和即可。

###python

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.cnt = Counter(nums2)
        self.nums1 = nums1
        self.nums2 = nums2

    def add(self, index: int, val: int) -> None:
        self.cnt[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.cnt[self.nums2[index]] += 1

    def count(self, tot: int) -> int:
        return sum(self.cnt[tot - x] for x in self.nums1)


# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

###java

class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private Map<Integer, Integer> cnt = new HashMap<>();

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        for (int x : nums2) {
            cnt.merge(x, 1, Integer::sum);
        }
    }

    public void add(int index, int val) {
        cnt.merge(nums2[index], -1, Integer::sum);
        nums2[index] += val;
        cnt.merge(nums2[index], 1, Integer::sum);
    }

    public int count(int tot) {
        int ans = 0;
        for (int x : nums1) {
            ans += cnt.getOrDefault(tot - x, 0);
        }
        return ans;
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs obj = new FindSumPairs(nums1, nums2);
 * obj.add(index,val);
 * int param_2 = obj.count(tot);
 */

###cpp

class FindSumPairs {
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;
        this->nums2 = nums2;
        for (int x : nums2) {
            ++cnt[x];
        }
    }

    void add(int index, int val) {
        --cnt[nums2[index]];
        nums2[index] += val;
        ++cnt[nums2[index]];
    }

    int count(int tot) {
        int ans = 0;
        for (int x : nums1) {
            ans += cnt[tot - x];
        }
        return ans;
    }

private:
    vector<int> nums1;
    vector<int> nums2;
    unordered_map<int, int> cnt;
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(nums1, nums2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

###go

type FindSumPairs struct {
nums1 []int
nums2 []int
cnt   map[int]int
}

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
cnt := map[int]int{}
for _, x := range nums2 {
cnt[x]++
}
return FindSumPairs{nums1, nums2, cnt}
}

func (this *FindSumPairs) Add(index int, val int) {
this.cnt[this.nums2[index]]--
this.nums2[index] += val
this.cnt[this.nums2[index]]++
}

func (this *FindSumPairs) Count(tot int) (ans int) {
for _, x := range this.nums1 {
ans += this.cnt[tot-x]
}
return
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * obj := Constructor(nums1, nums2);
 * obj.Add(index,val);
 * param_2 := obj.Count(tot);
 */

###ts

class FindSumPairs {
    private nums1: number[];
    private nums2: number[];
    private cnt: Map<number, number>;

    constructor(nums1: number[], nums2: number[]) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.cnt = new Map();
        for (const x of nums2) {
            this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
        }
    }

    add(index: number, val: number): void {
        const old = this.nums2[index];
        this.cnt.set(old, this.cnt.get(old)! - 1);
        this.nums2[index] += val;
        const now = this.nums2[index];
        this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
    }

    count(tot: number): number {
        return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * var obj = new FindSumPairs(nums1, nums2)
 * obj.add(index,val)
 * var param_2 = obj.count(tot)
 */

###rust

use std::collections::HashMap;

struct FindSumPairs {
    nums1: Vec<i32>,
    nums2: Vec<i32>,
    cnt: HashMap<i32, i32>,
}

impl FindSumPairs {
    fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
        let mut cnt = HashMap::new();
        for &x in &nums2 {
            *cnt.entry(x).or_insert(0) += 1;
        }
        Self { nums1, nums2, cnt }
    }

    fn add(&mut self, index: i32, val: i32) {
        let i = index as usize;
        let old_val = self.nums2[i];
        *self.cnt.entry(old_val).or_insert(0) -= 1;
        if self.cnt[&old_val] == 0 {
            self.cnt.remove(&old_val);
        }

        self.nums2[i] += val;
        let new_val = self.nums2[i];
        *self.cnt.entry(new_val).or_insert(0) += 1;
    }

    fn count(&self, tot: i32) -> i32 {
        let mut ans = 0;
        for &x in &self.nums1 {
            let target = tot - x;
            if let Some(&c) = self.cnt.get(&target) {
                ans += c;
            }
        }
        ans
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * let mut obj = FindSumPairs::new(nums1, nums2);
 * obj.add(index, val);
 * let ret_2: i32 = obj.count(tot);
 */

###js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 */
var FindSumPairs = function (nums1, nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    this.cnt = new Map();
    for (const x of nums2) {
        this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
    }
};

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
FindSumPairs.prototype.add = function (index, val) {
    const old = this.nums2[index];
    this.cnt.set(old, this.cnt.get(old) - 1);
    this.nums2[index] += val;
    const now = this.nums2[index];
    this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
};

/**
 * @param {number} tot
 * @return {number}
 */
FindSumPairs.prototype.count = function (tot) {
    return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * var obj = new FindSumPairs(nums1, nums2)
 * obj.add(index,val)
 * var param_2 = obj.count(tot)
 */

###cs

public class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private Dictionary<int, int> cnt = new Dictionary<int, int>();

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        foreach (int x in nums2) {
            if (cnt.ContainsKey(x)) {
                cnt[x]++;
            } else {
                cnt[x] = 1;
            }
        }
    }

    public void Add(int index, int val) {
        int oldVal = nums2[index];
        if (cnt.TryGetValue(oldVal, out int oldCount)) {
            if (oldCount == 1) {
                cnt.Remove(oldVal);
            } else {
                cnt[oldVal] = oldCount - 1;
            }
        }
        nums2[index] += val;
        int newVal = nums2[index];
        if (cnt.TryGetValue(newVal, out int newCount)) {
            cnt[newVal] = newCount + 1;
        } else {
            cnt[newVal] = 1;
        }
    }

    public int Count(int tot) {
        int ans = 0;
        foreach (int x in nums1) {
            int target = tot - x;
            if (cnt.TryGetValue(target, out int count)) {
                ans += count;
            }
        }
        return ans;
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs obj = new FindSumPairs(nums1, nums2);
 * obj.Add(index,val);
 * int param_2 = obj.Count(tot);
 */

时间复杂度 $O(n \times q)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别是数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度，而 $q$ 是调用 $\text{count}$ 方法的次数。

---

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

1. 累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
2. 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

• FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
• void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
• int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

 

示例：

输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：
[null, 8, null, 2, 1, null, null, 11]

解释：
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7

 

提示：

• 1 <= nums1.length <= 1000
• 1 <= nums2.length <= 105
• 1 <= nums1[i] <= 109
• 1 <= nums2[i] <= 105
• 0 <= index < nums2.length
• 1 <= val <= 105
• 1 <= tot <= 109
• 最多调用 add 和 count 函数各 1000 次

###python

from collections import Counter

class FindSumPairs:
    def __init__(self, nums1, nums2):
        self.n2 = nums2
        self.d1 = Counter(nums1)
        self.d2 = Counter(nums2)

    def add(self, index: int, val: int):
        tmp = self.n2[index]
        self.n2[index] = tmp + val
        self.d2[tmp] -= 1
        self.d2[tmp + val] += 1
        
    def count(self, tot: int) -> int:
        tmp = 0
        for k, v in self.d1.items():
            tmp += v * self.d2.get(tot - k, 0)
        return tmp

本质是 1. 两数之和。

遍历 $\textit{nums}_1$ 中的数，问题变成：

• 设 $x = \textit{nums}_1[i]$，计算 $\textit{nums}_2$ 中有多少个数等于 $\textit{tot} - x$。

用哈希表维护 $\textit{nums}_2$ 中每个元素的出现次数，即可 $\mathcal{O}(1)$ 获知。

注：遍历 $\textit{nums}_1$ 中的数，是因为数据范围显示 $\textit{nums}_1$ 的最大长度比 $\textit{nums}_2$ 的小，遍历 $\textit{nums}_1$ 相比遍历 $\textit{nums}_2$ 时间复杂度更低。

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.cnt = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        # 维护 nums2 每个元素的出现次数
        self.cnt[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.cnt[self.nums2[index]] += 1

    def count(self, tot: int) -> int:
        ans = 0
        for x in self.nums1:
            ans += self.cnt[tot - x]
        return ans

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums2 = nums2
        self.cnt1 = Counter(nums1)
        self.cnt2 = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        # 维护 nums2 每个元素的出现次数
        self.cnt2[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.cnt2[self.nums2[index]] += 1

    def count(self, tot: int) -> int:
        ans = 0
        for x, c1 in self.cnt1.items():
            ans += c1 * self.cnt2[tot - x]
        return ans

class FindSumPairs {
    private final int[] nums1;
    private final int[] nums2;
    private final Map<Integer, Integer> cnt = new HashMap<>();

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        for (int x : nums2) {
            cnt.merge(x, 1, Integer::sum);
        }
    }

    public void add(int index, int val) {
        // 维护 nums2 每个元素的出现次数
        cnt.merge(nums2[index], -1, Integer::sum);
        nums2[index] += val;
        cnt.merge(nums2[index], 1, Integer::sum);
    }

    public int count(int tot) {
        int ans = 0;
        for (int x : nums1) {
            ans += cnt.getOrDefault(tot - x, 0);
        }
        return ans;
    }
}

class FindSumPairs {
    vector<int> nums1, nums2;
    unordered_map<int, int> cnt;

public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;
        this->nums2 = nums2;
        for (int x : nums2) {
            cnt[x]++;
        }
    }

    void add(int index, int val) {
        // 维护 nums2 每个元素的出现次数
        cnt[nums2[index]]--;
        nums2[index] += val;
        cnt[nums2[index]]++;
    }

    int count(int tot) {
        int ans = 0;
        for (int x : nums1) {
            ans += cnt[tot - x];
        }
        return ans;
    }
};

type FindSumPairs struct {
nums1 []int
nums2 []int
cnt   map[int]int
}

func Constructor(nums1, nums2 []int) FindSumPairs {
cnt := map[int]int{}
for _, x := range nums2 {
cnt[x]++
}
return FindSumPairs{nums1, nums2, cnt}
}

func (p *FindSumPairs) Add(index, val int) {
// 维护 nums2 每个元素的出现次数
p.cnt[p.nums2[index]]--
p.nums2[index] += val
p.cnt[p.nums2[index]]++
}

func (p *FindSumPairs) Count(tot int) (ans int) {
for _, x := range p.nums1 {
ans += p.cnt[tot-x]
}
return
}

复杂度分析

• 时间复杂度：初始化是 $\mathcal{O}(m)$，$\texttt{add}$ 是 $\mathcal{O}(1)$，$\texttt{count}$ 是 $\mathcal{O}(n)$。其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
• 空间复杂度：$\mathcal{O}(m+q)$。其中 $q$ 是 $\texttt{add}$ 的调用次数。代码没有删除哈希表中出现次数等于 $0$ 的元素。

相似题目

2671. 频率跟踪器

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。

• 如果数组中存在多个幸运数，只需返回 最大 的那个。
• 如果数组中不含幸运数，则返回 -1 。

 

示例 1：

输入：arr = [2,2,3,4]
输出：2
解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。

示例 2：

输入：arr = [1,2,2,3,3,3]
输出：3
解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。

示例 3：

输入：arr = [2,2,2,3,3]
输出：-1
解释：数组中不存在幸运数。

示例 4：

输入：arr = [5]
输出：-1

示例 5：

输入：arr = [7,7,7,7,7,7,7]
输出：7

 

提示：

• 1 <= arr.length <= 500
• 1 <= arr[i] <= 500

方法一：哈希表

用哈希表统计每个元素的出现次数。

然后遍历哈希表，其中 key 等于 value 的元素即为幸运数，取其最大值。如果不存在这样的元素，答案为 $-1$。

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        ans = -1
        for x, c in cnt.items():
            if x == c:
                ans = max(ans, x)
        return ans

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        return max((x for x, c in cnt.items() if x == c), default=-1) 

###java

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : arr) {
            cnt.merge(x, 1, Integer::sum);
        }

        int ans = -1;
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            int x = e.getKey();
            int c = e.getValue();
            if (x == c) {
                ans = Math.max(ans, x);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> cnt;
        for (int x : arr) {
            cnt[x]++;
        }

        int ans = -1;
        for (auto& [x, c] : cnt) {
            if (x == c) {
                ans = max(ans, x);
            }
        }
        return ans;
    }
};

###go

func findLucky(arr []int) int {
cnt := map[int]int{}
for _, x := range arr {
cnt[x]++
}

ans := -1
for x, c := range cnt {
if x == c {
ans = max(ans, x)
}
}
return ans
}

###js

var findLucky = function(arr) {
    const cnt = new Map();
    for (const x of arr) {
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }

    let ans = -1;
    for (const [x, c] of cnt.entries()) {
        if (x === c) {
            ans = Math.max(ans, x);
        }
    }
    return ans;
};

###rust

use std::collections::HashMap;

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        for x in arr {
            *cnt.entry(x).or_insert(0) += 1;
        }

        let mut ans = -1;
        for (x, c) in cnt {
            if x == c {
                ans = ans.max(x);
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：数组

由于一个数的出现次数不可能大于 $n$，所以大于 $n$ 的元素一定不是幸运数。我们只需统计 $\le n$ 的元素出现次数。

所以只需创建一个大小为 $n+1$ 的 $\textit{cnt}$ 数组统计。

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        n = len(arr)
        cnt = [0] * (n + 1)
        for x in arr:
            if x <= n:
                cnt[x] += 1

        for i in range(n, 0, -1):
            if cnt[i] == i:
                return i
        return -1

###java

class Solution {
    public int findLucky(int[] arr) {
        int n = arr.length;
        int[] cnt = new int[n + 1];
        for (int x : arr) {
            if (x <= n) {
                cnt[x]++;
            }
        }

        for (int i = n; i > 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

###cpp

class Solution {
public:
    int findLucky(vector<int>& arr) {
        int n = arr.size();
        vector<int> cnt(n + 1);
        for (int x : arr) {
            if (x <= n) {
                cnt[x]++;
            }
        }

        for (int i = n; i > 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
};

###c

int findLucky(int* arr, int arrSize) {
    int* cnt = calloc(arrSize + 1, sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] <= arrSize) {
            cnt[arr[i]]++;
        }
    }

    for (int i = arrSize; i > 0; i--) {
        if (cnt[i] == i) {
            free(cnt);
            return i;
        }
    }
    free(cnt);
    return -1;
}

###go

func findLucky(arr []int) int {
n := len(arr)
cnt := make([]int, n+1)
for _, x := range arr {
if x <= n {
cnt[x]++
}
}

for i := n; i >= 1; i-- {
if cnt[i] == i {
return i
}
}
return -1
}

###js

var findLucky = function(arr) {
    const n = arr.length;
    const cnt = Array(n + 1).fill(0);
    for (const x of arr) {
        if (x <= n) {
            cnt[x]++;
        }
    }

    for (let i = n; i > 0; i--) {
        if (cnt[i] === i) {
            return i;
        }
    }
    return -1;
};

###rust

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut cnt = vec![0; n + 1];
        for x in arr {
            if x as usize <= n {
                cnt[x as usize] += 1;
            }
        }

        for i in (1..=n).rev() {
            if cnt[i] as usize == i {
                return i as _;
            }
        }
        -1
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

思考题

动态地往 $\textit{arr}$ 中添加、删除元素，每次操作后，输出最大幸运数（不存在则为 $-1$）。

具体来说，额外输入一个 $\textit{queries}$ 数组，其中 $\textit{queries}[i] = [\textit{op}, x]$，如果 $\textit{op}=1$ 表示往 $\textit{arr}$ 中添加一个 $x$；如果 $\textit{op}=2$ 表示删除 $\textit{arr}$ 中的一个 $x$。你需要返回一个与 $\textit{queries}$ 等长的数组，表示每次操作后的答案。

欢迎在评论区分享你的思路/代码。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

计数器法,然后倒叙便利计数器中的值, 若下标的值 == 出现的次数, 则直接返回即可(此时即为最大值)

class Solution {
    public int findLucky(int[] arr) {
        int[] temp = new int[501];
        // 将出现次数存入计数器
        for (int i : arr) {
            temp[i]++;
        }

        // 倒叙便利计数器中的值, 若下标的值 == 出现的次数, 则直接返回即可(此时即为最大值)
        for (int i = temp.length - 1; i >= 1; i--) {
            if (i == temp[i]) {
                return i;
            }
        }

        // 说明没有幸运数
        return -1;
    }
}

方法一：哈希映射

思路

我们可以使用哈希映射来解决这个问题，把数值作为键，把数值出现的次数作为值。具体地，我们先遍历原数组建立哈希表，然后遍历哈希表找到最大的键和值相等的元素作为答案，如果找不到就返回 -1。

代码

###C++

class Solution {
public:
    unordered_map <int, int> m;
    int findLucky(vector<int>& arr) {
        for (auto x: arr) {
            ++m[x];
        }
        int ans = -1;
        for (auto [key, value]: m) {
            if (key == value) {
                ans = max(ans, key);
            }
        }
        return ans;
    }
};

###Python

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        m = dict()
        for x in arr:
            m[x] = m.get(x, 0) + 1
        ans = -1
        for (key, value) in m.items():
            if key == value:
                ans = max(ans, key)
        return ans

###Java

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int x : arr) {
            m.put(x, m.getOrDefault(x, 0) + 1);
        }
        int ans = -1;
        for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
            int key = entry.getKey(), value = entry.getValue();
            if (key == value) {
                ans = Math.max(ans, key);
            }
        }
        return ans;
    }
}

###C#

public class Solution {
    public int FindLucky(int[] arr) {
        Dictionary<int, int> m = new Dictionary<int, int>();
        foreach (int x in arr) {
            if (m.ContainsKey(x)) {
                m[x]++;
            } else {
                m[x] = 1;
            }
        }
        int ans = -1;
        foreach (var kvp in m) {
            if (kvp.Key == kvp.Value) {
                ans = Math.Max(ans, kvp.Key);
            }
        }
        return ans;
    }
}

###Go

func findLucky(arr []int) int {
    m := make(map[int]int)
    for _, x := range arr {
        m[x]++
    }
    ans := -1
    for key, value := range m {
        if key == value {
            ans = max(ans, key)
        }
    }
    return ans
}

###C

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = val;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, int key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, int key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);
    }
}

int findLucky(int* arr, int arrSize) {
    HashItem *m = NULL;
    for (int i = 0; i < arrSize; i++) {
        hashSetItem(&m, arr[i], hashGetItem(&m, arr[i], 0) + 1);
    }
    int ans = -1;
    for (HashItem *pEntry = m; pEntry; pEntry = pEntry->hh.next) {
        if (pEntry->key == pEntry->val) {
            ans = fmax(ans, pEntry->key);
        }
    }
    hashFree(&m);
    return ans;
}

###JavaScript

var findLucky = function(arr) {
    let m = {}
    arr.forEach((x) => {
        m[x] = (x in m ? m[x] + 1 : 1)
    })
    let ans = -1
    Object.keys(m).forEach((key) => {
        ans = (key == m[key] ? Math.max(key, ans) : ans)
    })
    return ans
};

###TypeScript

function findLucky(arr: number[]): number {
    const m = new Map<number, number>();
    for (const x of arr) {
        m.set(x, (m.get(x) || 0) + 1);
    }
    let ans = -1;
    for (const [key, value] of m) {
        if (key === value) {
            ans = Math.max(ans, key);
        }
    }
    return ans;
};

###Rust

use std::collections::HashMap;

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut m = HashMap::new();
        for x in arr {
            *m.entry(x).or_insert(0) += 1;
        }
        let mut ans = -1;
        for (&key, &value) in m.iter() {
            if key == value {
                ans = ans.max(key);
            }
        }
        ans
    }
}

复杂度分析

记数组中的的元素个数为 $n$，则哈希表中最多有 $n$ 个键值对。

• 时间复杂度：遍历数组的时间代价是 $O(n)$，遍历哈希表的时间代价也是 $O(n)$，故渐进时间复杂度 $O(n)$。

• 空间复杂度：哈希表中最多有 $n$ 个键值对，故渐进空间复杂度 $O(n)$。