与えられた条件を満たす配列内のペアの数を見つけるためのC++プログラム

配列numsにn個の数値が与えられているとします。配列から2つの数値のペアを選択する必要があり、配列内のそれらの位置の差が2つの数値の合計に等しいという条件があります。与えられた数の配列から、合計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