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

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

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

उदाहरण के लिए, यदि इनपुट [1,2,3,4] है, तो आउटपुट 3 होगा, क्योंकि तत्व [1,2,3], [2,3,4] और [1,2,3,4] हैं।

हल करने के चरण

• ret := 0, n := A का आकार, आकार n की एक सरणी dp बनाएं
• i को 2 से n-1 तक लूप करें
  • यदि A[i] - A[i-1] = A[i-1] - A[i-2], तो
    • dp[i] := 1 + dp[i-1]
    • ret को 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]

आउटपुट

3