अंकगणितीय स्लाइस II - सी++ में परवर्ती

मान लीजिए कि हमारे पास एक सरणी A है, जहाँ N संख्याएँ मौजूद हैं। उस सरणी का एक अनुवर्ती टुकड़ा पूर्णांकों का कोई भी क्रम है जैसे (K0, K1, K2, … Kn) जैसे कि 0 <=K0 =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],

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

• रिट:=0
• एक मानचित्र डीपी दूसरे मानचित्र को परिभाषित करें
• ए से तत्वों को लेकर एक सेट को परिभाषित करें
• n :=A का आकार
• इनिशियलाइज़ i :=1 के लिए, जब i करें
• इनिशियलाइज़ j :=i-1 के लिए, जब j>=0, अपडेट करें (j को 1 से घटाएं), −
  करें
  • diff :=A[i] - A[j]
  • यदि diff <=-inf या diff> inf, तो −
    • निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
  • अस्थायी:=dp[j, diff] जब मानचित्र dp[j] में भिन्न हो, अन्यथा 0
  • रिट:=रिट + अस्थायी
  • यदि (A[i] + diff) s में मौजूद है, तो −
    • dp[i, diff] :=dp[i, diff] + temp + 1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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