昨天的
題目：
有一個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
坐火車很無聊
看不到今天的題目
用昨天的先水一篇
對阿