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

Z时代
2024-01-10
分类：综合

假设给定数组 nums 中的 n 个数字。我们必须从数组中选择一对两个数，并且有一个条件是它们在数组中的位置之差等于两个数之和。从给定的数字数组中，总共可以有 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;
}