C++程序：查找数组中满足给定条件的数对个数

假设我们有一个包含n个数字的数组nums。我们必须从数组中选择一对数字，并且有一个条件是它们在数组中的位置差等于这两个数字之和。从给定的数字数组中，最多可以有n(n - 1)/2个可能的数对。我们必须找出数组中满足此条件的数对的总数。

因此，如果输入为n = 8，nums = {4, 2, 1, 0, 1, 2, 3, 3}，则输出为13。

数组中可能有13个这样的数对。

为了解决这个问题，我们将遵循以下步骤：

Define an array vals(n)
for initialize i := 0, when i < n, update (increase i by 1), do:
   vals[i] := i + 1 - nums[i]
sort the array vals
res := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   k := nums[i] + i + 1
res := res + (position of first occurrence of a value not less than k in array vals - position of first occurrence of a value not greater than k in array vals)
return res

示例

让我们看下面的实现来更好地理解：

#include <bits/stdc++.h>
using namespace std;

int solve(int n, vector<int> nums){
   vector<int> vals(n);
   for( int i = 0; i < n; i++)
      vals[i] = i + 1 - nums[i]; 
   sort(vals.begin(), vals.end());
   int res = 0;
   for( int i = 0; i < n; i++ ) {
      int k = nums[i] + i + 1;
      res += upper_bound(vals.begin(), vals.end(), k) - lower_bound(vals.begin(), vals.end(), k);
   }
   return res;
}
int main() {
   int n = 8;
   vector<int> nums = {4, 2, 1, 0, 1, 2, 3, 3};
   cout<< solve(n, nums);
   return 0;
}

输入

8, {4, 2, 1, 0, 1, 2, 3, 3}

输出

13

Arnab Chakraborty

更新于：2022年3月2日

2K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习