Arithmetic Slices II - ลำดับต่อมาใน C++

สมมติว่าเรามีอาร์เรย์ 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],

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=0
• กำหนดหนึ่งแผนที่ dp อีกแผนที่หนึ่ง cnt
• กำหนดหนึ่งชุดโดยนำองค์ประกอบจาก A
• n :=ขนาดของ A
• สำหรับการเริ่มต้น 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 + อุณหภูมิ
  • ถ้า (A[i] + diff) มีอยู่ใน s แล้ว −
    • dp[i, diff] :=dp[i, diff] + อุณหภูมิ + 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