C++ . में अंकगणितीय स्लाइस

मान लीजिए कि हमारे पास संख्याओं का एक क्रम है जिसे अंकगणित कहा जाता है यदि इसमें कम से कम तीन तत्व हों और यदि किन्हीं दो क्रमागत तत्वों के बीच का अंतर समान हो। तो उदाहरण के लिए, ये अंकगणितीय अनुक्रम हैं:[1, 3, 5, 7, 9], [7, 7, 7, 7], [3, -1, -5, -9], लेकिन निम्नलिखित अनुक्रम नहीं है अंकगणित। [1, 1, 2, 5, 7]

अब एक शून्य-अनुक्रमित सरणी A दिया गया है जिसमें N संख्याएँ हैं। उस दिए गए सरणी का एक टुकड़ा पूर्णांकों (पी, क्यू) की कोई भी जोड़ी है जैसे कि 0 <=पी <क्यू <एन। यहां सरणी ए का एक टुकड़ा (पी, क्यू) अंकगणित कहा जाता है यदि अनुक्रम:ए [पी], ए [पी + 1], ..., ए [क्यू -1], ए [क्यू] अंकगणित है। फ़ंक्शन को एरे ए में अंकगणितीय स्लाइस की संख्या का पता लगाना चाहिए।

तो अगर इनपुट [1,2,3,4] जैसा है, तो आउटपुट 3 होगा, क्योंकि तत्व [1,2,3], [2,3,4] और [1,2,3, 4]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ret:=0, n:=A का आकार, n आकार का dp सरणी बनाएं
• मैं 2 से n - 1 के बीच के लिए
  • यदि a[i] – a[i – 1] =a[i – 1] – a[i – 2], तो
    • dp[i] :=1 + dp[i - 1]
    • dp द्वारा बढ़ाएँ[i]
• रिटर्न रिटर्न

उदाहरण (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]

आउटपुट

3