数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中查找排序数组中和小于x的数对
给定一个整数类型的排序数组和一个整数变量x，任务是从给定数组中形成数对，计算数对中元素的和，并检查计算出的和是否小于x。
输入 − int arr[] = {2, 7, 1, 0, 8}, int x = 8
输出 − 排序数组中和小于x的数对的数量为 - 4
解释 − 从给定数组中可以形成的数对有：(2, 7) = 9（大于x），(2, 1) = 3（小于x），(2, 0) = 2（小于x），(2, 8) = 10（大于x），(7, 1) = 8（等于x），(7, 0) = 7（小于x），(7, 8) = 15（大于x），(1, 0) = 1（小于x），(1, 8) = 8（等于x），(0, 8) = 8（等于x）。所以和小于x的数对是(4, 0)和(2, 2)。因此，和小于x的数对的数量为4。
输入 − int arr[] = {2, 4, 6, 8}, int x = 10
输出 − 排序数组中和小于x的数对的数量为 - 2
解释 − 从给定数组中可以形成的数对有：(2, 4) = 6（小于x），(2, 6) = 8（小于x），(2, 8) = 10（等于x），(4, 6) = 10（等于x），(4, 8) = 12（大于x），(6, 8) = 14（大于x）。所以，和小于x的数对的数量为2。
下面程序中使用的算法如下
解决给定问题有多种方法，即朴素方法和高效方法。因此，让我们首先看看朴素方法。
输入一个整数元素数组，计算数组的大小并将数据传递给函数
声明一个临时变量count来存储和小于x的数对的数量。
从i=0开始，循环FOR到数组的大小
在循环内部，从j=i+1开始，另一个循环FOR到数组的大小
在循环内部，计算和为arr[i] + arr[j]，并检查IF sum < x，则将count加1。
返回count
打印结果。
高效方法
输入一个整数元素数组，计算数组的大小并将数据传递给函数
声明一个临时变量count来存储和小于x的数对的数量。
将arr_0设置为0，将arr_1设置为size-1
从arr_0开始，循环FOR到arr_1
在循环内部，检查IF arr[arr_0] + arr[arr_1] < x，则将count设置为count + (arr_1 - arr_0)并递增arr_0++，否则将arr_1减1
返回count
打印结果。
示例（朴素方法）
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
int count = 0;
int sum = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
sum = arr[i] + arr[j];
if(sum < x){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {2, 7, 1, 0, 8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of pairs in a sorted array whose sum is less than x are: 4
示例（高效方法）
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
while(arr_0 < arr_1){
if (arr[arr_0] + arr[arr_1] < x){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {2, 7, 1, 0, 8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of pairs in a sorted array whose sum is less than x are: 4
568 次浏览
