पायथन में संख्याओं की सूची से अंकगणितीय उपअनुक्रमों की संख्या गिनने का प्रोग्राम

संख्याओं की सूची nums दी गई है। लंबाई ≥ 3 के अंकगणितीय उपअनुक्रमों (subsequences) की संख्या गिनें। अंकगणितीय अनुक्रम वह है जहां लगातार अंतर समान हो।

उदाहरण

इनपुट: nums = [6, 12, 13, 8, 10, 14]

आउटपुट: 3

उपअनुक्रम: [6, 8, 10], [6, 10, 14], [12, 13, 14]।

एल्गोरिदम (DP के साथ हैश मैप)

1. dp = डिक्शनरी जहां कुंजी (i, diff) = सूचकांक i पर समाप्त होने वाले अंतर diff वाले अंकगणितीय उपअनुक्रमों की संख्या (लंबाई ≥ 2)।
2. res = 0।
3. प्रत्येक i के लिए 0 से n-1:
   • प्रत्येक j के लिए 0 से i-1:
     • diff = nums[i] - nums[j]
     • prev = dp.get((i, diff), 0) (i पर समाप्त होने वाले मौजूदा अनुक्रम)
     • prevprev = dp.get((j, diff), 0) (j पर समाप्त होने वाले अनुक्रम)
     • dp[(i, diff)] = prev + prevprev + 1 (नया जोड़ा (j,i) + विस्तारित अनुक्रम)
     • res += prevprev (केवल लंबाई ≥ 3 वाले गिने जाते हैं)
4. res वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, nums):
        dp = {}
        n = len(nums)
        res = 0
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                prev = dp.get((i, diff), 0)
                prevprev = dp.get((j, diff), 0)
                dp[(i, diff)] = prev + prevprev + 1
                res += prevprev
        return res

# परीक्षण
ob = Solution()
print(ob.solve([6, 12, 13, 8, 10, 14]))  # 3
print(ob.solve([2, 4, 6, 8, 10]))        # 7

समय जटिलता

• O(n²) समय (नेस्टेड लूप)।
• O(n²) स्थान (सबसे खराब स्थिति में सभी जोड़े अलग-अलग अंतर देते हैं)।

लीटकोड संदर्भ

यह लीटकोड 446 "Arithmetic Slices II - Subsequence" के समान है। बड़े उत्तर के लिए मॉड्यूलो 10⁹+7 की आवश्यकता हो सकती है।