C++의 산술 조각

<시간/>

3개 이상의 요소로 구성되고 연속되는 두 요소의 차이가 동일한 경우 숫자 시퀀스를 산술이라고 가정합니다. 예를 들어, 이들은 산술 수열입니다:[1, 3, 5, 7, 9], [7, 7, 7, 7], [3, -1, -5, -9], 그러나 다음 수열은 산수. [1, 1, 2, 5, 7]

이제 N개의 숫자로 구성된 제로 인덱스 배열 A가 제공됩니다. 주어진 배열의 슬라이스는 0 <=P

따라서 입력이 [1,2,3,4]와 같으면 요소가 [1,2,3], [2,3,4] 및 [1,2,3]이므로 출력은 3이 됩니다. 4]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=0, n :=A의 크기, n 크기의 배열 dp 생성
2 ~ n – 1 범위의 i에 대해
- a[i] – a[i – 1] =a[i – 1] – a[i – 2]이면
  - dp[i] :=1 + dp[i - 1]
  - dp[i]만큼 ret 증가
반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
      int numberOfArithmeticSlices(vector<int>& A) {
         int ret = 0;
         int n = A.size();
         vector <int> dp(n);
         for(int i = 2; i < n; i++){
            if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
               dp[i] = 1 + dp[i - 1];
               ret += dp[i];
            }
         }
         return ret;
      }  
};
main(){
   vector<int> v = {1,2,3,4};
   Solution ob;
   cout << (ob.numberOfArithmeticSlices(v));
}

입력

[1,2,3,4]