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

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

उदाहरण

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

आउटपुट: 4

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

एल्गोरिदम (रैखिक स्कैन)

1. count = 0 (वर्तमान अंकगणितीय स्ट्रीक की लंबाई - 2), ans = 0।
2. i = 2 से len(nums)-1 तक:
   • यदि nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
     • count += 1
   • अन्यथा:
     • ans += count * (count + 1) // 2
     • count = 0
3. लूप के बाद, यदि count > 0: ans += count * (count + 1) // 2।
4. ans वापस करें।

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

class Solution:
    def solve(self, nums):
        count = 0
        ans = 0
        for i in range(2, len(nums)):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                count += 1
            else:
                ans += count * (count + 1) // 2
                count = 0
        if count:
            ans += count * (count + 1) // 2
        return ans

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

गणित

यदि k लगातार तत्व समान अंतर वाले हैं (लंबाई k+2), तो उनमें लंबाई ≥ 3 के सन्निकट अंकगणितीय उपसरणियों की संख्या = 1 + 2 + ... + k = k(k+1)/2।

समय जटिलता

• O(n) समय, O(1) स्थान।
• उपअनुक्रम (गैर-सन्निकट) संस्करण O(n²) है।

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

लीटकोड 413 "Arithmetic Slices"।