C++에서 1이 다른 연속 요소가 있는 하위 배열 계산

<시간/>

정수를 포함하는 배열 arr[]이 제공됩니다. 목표는 각 하위 배열의 연속 요소가 1만 달라지도록 하는 모든 하위 배열을 계산하는 것입니다. 배열이 [1,2,3]이면 하위 배열은 [1,2], [2,3], [1,2,3]만 됩니다.

예를 들어 이해합시다.

입력 - arr[] ={ 4,3,2,1 };

출력 − 연속 요소가 1만큼 다른 하위 배열의 개수는 − 6입니다.

설명 − Subaarays는 −

[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입니다.

설명 − Subaarays는 −

[5,6], [6,7], [5,6,7]. Total 3

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

for 루프를 사용하여 배열을 탐색합니다. i=0에서 i<크기까지. 그런 다음 인접한 요소와 1만큼 다른 요소가 있는지 확인합니다. 그렇다면 인덱스를 첫 번째로 저장합니다. 그렇지 않은 경우 하위 배열의 요소 수를 임시로 사용합니다( 처음부터 마지막으로 +1 ). 인덱스 첫 번째와 마지막 사이의 배열은 모든 연속 요소가 1만큼 다릅니다. 따라서 전체 하위 배열은 temp*(temp-1)/2가 됩니다. 이것을 추가하여 계산합니다. 모든 연속 요소가 있는 다음 배열에 대한 인덱스 first=last=i를 업데이트합니다.

숫자의 배열 arr[]를 가져옵니다.
함수 sub_ele_diff_one(int arr[], int size)는 배열을 취하고 1이 다른 연속적인 요소가 있는 하위 배열의 수를 반환합니다.
초기 카운트를 0으로 합니다.
i=0에서 I 까지 for 루프를 사용하여 배열을 탐색합니다.
두 개의 변수를 먼저 취하고 모든 요소가 연속적이고 1만큼 다른 인덱스에 대해 마지막으로 0입니다.
arr[i-1]-arr[i] ==1 또는 arr[i]-arr[i-1]==1인지 확인합니다. (요소는 1씩 다름). true인 경우 먼저 증가합니다.
이전 조건이 false이면 이 조건을 충족하는 배열의 전체 요소는 temp=first-last+1입니다. 가능한 하위 배열은 total=temp*(temp-1)/2입니다.
이제 이 하위 배열 수 합계를 추가하여 계산합니다.
현재 I(연속 요소 조건이 실패하는 인덱스)으로 인덱스를 처음과 마지막으로 업데이트합니다.
for 루프의 끝에서 if first!=last. 이는 나머지 배열이 조건을 충족함을 의미합니다. 동일한 단계를 적용하고 합계를 계산에 추가합니다.
두 루프의 끝에서 결과로 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