题目:
题解:
思路:hashmap 计数
- 最近周赛脑筋急转弯的题目比较多,所以不能直接按题目的意思搞,需要进行转换。对于本题坏数对不好统计,所以直接统计好数对的数量,然后用总数对的数量减去好数对的数量即为坏数对的个数。
代码如下:
using LL = long long; class Solution { public: long long countBadPairs(vector& a) { unordered_map cnt; LL res=0; int n=a.size(); for(int i=0;i if(cnt.count(i-a[i]))res+=cnt[i-a[i]]; cnt[i-a[i]]++; } return 1LL*n*(n-1)/2-res; } };