找出阵列中(i，j)对的总数，以使i <j且a [i] + a [j] = i + j. [英] Find total number of (i,j) pairs in an array such that i&lt;j and a[i]+a[j]=i+j.

问题描述

我有一个使用两个循环的幼稚解决方案，但我想将时间复杂度提高为O(nlogn).有更好的方法吗?

I have a naive solution which uses two loops, but I want to improve the time complexity as O(nlogn). Any better approach available?

该数组未排序，并且也可以具有负值.

The array is unsorted and can have negative values too.

样本测试用例: 数组:1 0 3 2

Sample Test Case: Array: 1 0 3 2

输出: 4

说明: 索引-(0,1)，(0,3)，(1,2)，(2,3)是满足给定约束的对.

Explanation: Indices - (0,1), (0,3), (1,2), (2,3) are the pairs which satisfy the given constraints.

推荐答案

问题:find (i,j), i<j, s.t. a[i] + a[j] = i + j

我提出以下方法:

1. 设置b[i] = a[i] - i
   问题变为:find (i,j), i<j, s.t. b[i] + b[j] = 0
   复杂度:O(n)

1. Set b[i] = a[i] - i
   The problem becomes: find (i,j), i<j, s.t. b[i] + b[j] = 0
   Complexity: O(n)

在std :: vector(或std :: array)中创建对象c[i] = (b[i],i)(例如，结构)
复杂度:O(n)

Create objects c[i] = (b[i],i), a struct for example, in a std::vector (or std::array)
Complexity: O(n)

根据b值对c[i]对进行排序->获得d[j] = (v[j], i[j])，对数组进行排序
复杂度:O(nlogn)

Sort the c[i] pairs according to b values -> get d[j] = (v[j], i[j]) , sorted array
Complexity: O(nlogn)

查找所有对j,k，使v[j] = -v[k]
复杂性:要排序的数组应为O(n)

Find all pairs j,k such that v[j] = -v[k]
Complexity: the array being sorted, should be O(n)

保持案例i[j] < i[k]
复杂度:O(n)

keep the cases i[j] < i[k]
Complexity: O(n)

这篇关于找出阵列中(i，j)对的总数，以使i <j且a [i] + a [j] = i + j.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！