2364: Count-Number-of-Bad-Pairs
Medium
table of contents
I think seeing the vision trivialises the
solution of this problem. The key trick to realise is that the condition
j - i != nums[j] - nums[i]
can be rearranged as
j - nums[j] != i - nums[i]
.
Then, we can just use an unordered_map
(hashmap) to track the count good pairs and
subtract of the number of total pairs to get the number
of bad pairs.
Note, that the number of total pairs is
just (n-1) + (n-2) + ... + 2 + 1 = n * (n-1) / 2
.
code
class Solution {
public:
long long countBadPairs(vector<int>& nums) {
long long n = nums.size();
long long ans = n * (n-1) / 2;
<int, long long> mp;
unordered_maplong long good_pair_count = 0;
for (int i = 0; i < n; ++i) {
++mp[i-nums[i]];
}
for (auto const& [key, value] : mp) {
+= value*(value-1)/2;
good_pair_count }
return ans - good_pair_count;
}
};