题面大意
给出一个数组,在数组当中找到满足i<ji < ji<j 并且aj−ai=j−ia_j - a_i = j - iaj −ai =j−i的对数,输出一共多少对。
思路解析
* 因为条件$i < j $,因此根据这个条件可以确定对数一定是从左往右选择,并且不会有对数重复选择的情况。
* 根据条件变式一下,条件为aj−ai=j−ia_j - a_i = j - iaj −ai =j−i,我们交换下未知数,可得ai−i=aj−ja_i - i = a _j - jai −i=aj −j 则为我们要求的答案。通过这个变式,我们可以将选取两个数字作比较的操作,变为求解得到相同数字的aia_iai 有几个则为正确答案。
时间复杂度
只需要计算每个数字-自身下标的情况累加即可,时间复杂度O(n)O(n)O(n)
代码演示