本质是 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站@灵茶山艾府

方法一：哈希表

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

然后遍历哈希表，其中 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站@灵茶山艾府