LeetCode 5761. 找出和为指定值的下标对
原题链接
中等
作者:
YimingLi
,
2021-05-16 12:02:38
,
所有人可见
,
阅读 350
5761. Finding Pairs With a Certain Sum
算法 —— map 查询
- 注意到
nums1
的数的个数比较小,因此查询 tot
的时候,可以枚举 nums1
里面所有的数 a
,在 nums2
里面查询 tot-a
的个数
- 初始化的时候需要同时初始化
map
用来存储 nums2
里面每个数的个数
- 更新的时候同步维护
map
时间复杂度
- 构造:
O(nums2.length)
- 添加:
O(1)
- 统计:
O(nums1.length)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
class FindSumPairs {
public:
vector<int> nums1, nums2;
unordered_map<int, int> cnt2;
FindSumPairs(vector<int>& _nums1, vector<int>& _nums2) {
nums1 = _nums1, nums2 = _nums2;
for (auto& a : nums2) {
cnt2[a]++;
}
}
void add(int index, int val) {
int old = nums2[index];
nums2[index] += val;
cnt2[old]--, cnt2[nums2[index]]++;
}
int count(int tot) {
int ans = 0;
for (auto& a : nums1) {
int val = tot - a;
if (cnt2.count(val)) ans += cnt2[val];
}
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);
*/