数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于：2022年3月2日
2K+ 次浏览
广告