网站跳转怎么做360/发稿软文公司

        刷一道中等难度题目，思路和别人的一样，结果我的判定timeout， 后来发现，是我使用的list查找耽误事啦！哎。

6142. 统计坏数对的数目

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

思路：

• 先求n个数两两组合的总数目减去可以配对的总数目。
• 可以配对的总数目减去可组非坏数对的数目即为所求。
• 求非坏数对的数目问题转换为num[i]与下标i的差值相同的组合。有2个以上就能组成非数对。

        timeout版本的代码，我是考虑让第一遍出来只保留与下标差相同的组合对数，就用appe存储某个下标差是否出现过，yes字典结构存储有2个及以上出现的次数。结果应该是每次list查询是否出现耽误了时间，导致代码timeout。

        所以，后来丢弃了appe，直接用yes存储下标差出现的次数，这样通过了所有测试用例。

timeout代码：

class Solution:def countBadPairs(self, nums: List[int]) -> int:n=len(nums)appe=[]yes={}for i,v in enumerate(nums):if v-i not in appe:appe.append(v-i)else:if v-i not in yes :yes[v-i]=2else:yes[v-i]+=1n_match=0dp=[-1]*(n+1)for v in yes:if dp[yes[v]]==-1:dp[yes[v]]=yes[v]*(yes[v]-1)//2n_match+=dp[yes[v]]return n*(n-1)//2-n_match

pass代码： 

class Solution:def countBadPairs(self, nums: List[int]) -> int:n=len(nums)yes={}for i,v in enumerate(nums):if v-i not in yes:yes[v-i]=1else:yes[v-i]+=1n_match=0dp=[-1]*(n+1)for v in yes:if yes[v]>1:if dp[yes[v]]==-1:dp[yes[v]]=yes[v]*(yes[v]-1)//2n_match+=dp[yes[v]]return n*(n-1)//2-n_match