昨天的
题目：
有一个array叫nums里面有很多数字
我们要找里面有几对符合i<j且nums[j]-nums[i]!=j-i
思路：
先去算有几对符合nums[j]-nums[i]!=j-i
再用全部去扣
nums[j]-nums[i]=j-i移项可以变成nums[j]-j=nums[i]-i
所以可以先把nums每项都先改成nums[i]-i
再去统计每个数字出现的频率
假设一个数字出现k次
因为要k个找两个做组合所以就有k*(k-1)/2对
每一项加起来再用全部去扣就是答案了
Code:
def countBadPairs(self, nums):
for i in range(len(nums)):
nums[i]-=i
dict={}
total=len(nums)*(len(nums)-1)//2
for i in nums:
if i not in dict:
dict[i]=1
else:
dict[i]+=1
for i in dict:
total-=dict[i]*(dict[i]-1)//2
return total
坐火车很无聊
看不到今天的题目
用昨天的先水一篇
对阿