数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中计算元素差值为1的连续子数组个数
给定一个包含整数的数组arr[]。目标是计算arr[]的所有子数组的个数，使得每个子数组中连续元素之间的差值仅为1。如果数组是[1,2,3]，子数组将只有[1,2]，[2,3]，[1,2,3]。
让我们通过例子来理解。
输入 − arr[] = { 4,3,2,1 };
输出 − 元素差值为1的连续子数组个数为 − 6
解释 − 子数组将为 −
[4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1]. Total 6.
输入 − arr[] = { 1,5,6,7,9,11 };
输出 − 元素差值为1的连续子数组个数为 − 3
解释 − 子数组将为 −
[5,6], [6,7], [5,6,7]. Total 3
下面程序中使用的方法如下
我们将使用for循环遍历数组。从i=0到i<size。然后检查是否有任何元素与其相邻元素的差值为1。如果是，则将索引存储为first。如果不是，则将子数组中的元素个数作为temp (first-last +1)。索引first和last之间的数组都具有差值为1的连续元素。因此，子数组总数将为temp*(temp-1)/2。将其添加到count中。为下一个所有连续元素的数组更新索引first=last=i。
取一个数字数组arr[]。
函数sub_ele_diff_one(int arr[], int size)接受数组并返回差值为1的连续子数组的个数。
将初始计数设置为0。
我们将使用for循环遍历数组，从i=0到I <size。
取两个变量first、last为0，表示所有元素连续且差值为1的索引。
检查arr[i-1]-arr[i] ==1 OR arr[i]-arr[i-1]==1。（元素差值为1）。如果为真，则递增first。
如果之前的条件为假，则满足此条件的数组中的元素总数为temp=first-last+1。可能的子数组总数为total=temp*(temp-1)/2。
现在将此子数组计数total添加到count中。
使用当前I（连续元素条件失败的索引）更新索引first和last。
在for循环结束时，如果first!=last。这意味着剩余的数组满足条件。应用相同的步骤并将total添加到count中。
在两个循环结束时，返回count作为结果。
示例
#include <iostream>
using namespace std;
int sub_ele_diff_one(int arr[], int size){
int count = 0, first = 0, last = 0;
for (int i = 1; i < size; i++){
if (arr[i] - arr[i - 1] == 1 || arr[i-1] - arr[i] == 1){
first++;
}
else{
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
first = i;
last = i;
}
}
if (first != last){
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
}
return count;
}
int main(){
int arr[] = { 1, 2, 4, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of Subarrays with Consecutive elements differing by 1 are: "<<sub_ele_diff_one(arr, size);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of Subarrays with Consecutive elements differing by 1 are: 2
232 次浏览
