मान लीजिए हमारे पास एक सरणी A है, जहां N संख्याएं मौजूद हैं। उस सरणी का एक उपअनुक्रम स्लाइस किसी भी पूर्णांक अनुक्रम की तरह है जैसे (K0, K1, K2, ... Kn) जैसे कि 0 <= K0 < K1 < K2 < ... < Kn < N। A का एक उपअनुक्रम स्लाइस (K0, K1, K2, ... Kn) अंकगणितीय स्लाइस कहलाता है, यदि अनुक्रम A[K0], A[K1], ... A[Kn] अंकगणितीय है, इसका मतलब है कि n >= 2। तो हमें अंकगणितीय स्लाइस की संख्या लौटानी है।
तो यदि इनपुट [2,4,6,8,10] जैसा है, तो उत्तर 7 होगा, क्योंकि 7 अंकगणितीय स्लाइस हैं। [2,4,6], [2,4,10], [4,6,8], [6,8,10], [2,4,6,8], [4,6,8,10], [2,4,6,8,10],
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- ret := 0
- एक मैप dp और एक मैप cnt परिभाषित करें
- A के तत्वों को लेकर एक सेट s परिभाषित करें
- n := A का आकार
- i := 1 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
- j := i - 1 से आरंभ करें, जब j >= 0, अपडेट करें (j को 1 से घटाएं), करें -
- diff := A[i] - A[j]
- यदि diff <= -inf या diff > inf, तो -
- निम्न भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
- temp := dp[j, diff] जब diff मैप dp[j] में है, अन्यथा 0
- ret := ret + temp
- यदि (A[i] + diff) s में मौजूद है, तो -
- dp[i, diff] := dp[i, diff] + temp + 1
- j := i - 1 से आरंभ करें, जब j >= 0, अपडेट करें (j को 1 से घटाएं), करें -
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int numberOfArithmeticSlices(vector<int>& A) { int ret = 0; unordered_map <lli, unordered_map <lli, lli> > dp, cnt; unordered_set <int> s (A.begin(), A.end()); int n = A.size(); for(int i = 1; i < n; i++){ for(int j = i - 1; j >= 0; j--){ lli diff = (lli)A[i] - (lli)A[j]; if(diff <= INT_MIN || diff > INT_MAX) continue; int temp = dp[j].count(diff) ? dp[j][diff] : 0; ret += temp; if(s.count(A[i] + diff))dp[i][diff] += temp + 1; } } return ret; } }; main(){ Solution ob; vector<int> v = {2,4,6,8,10}; cout << (ob.numberOfArithmeticSlices(v)); }इनपुट
{2,4,6,8,10}आउटपुट
7
