주어진 조건을 만족하는 배열의 쌍 수를 찾는 C++ 프로그램

<시간/>

배열 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;
}

입력

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