Python में सरणी से उन ट्रिपलेट्स की संख्या जांचें जिनका योग लक्ष्य से कम है

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान target है, हमें उन ट्रिपल (i < j < k) की संख्या ढूंढनी है जो मौजूद हैं जैसे कि nums[i] + nums[j] + nums[k] < target।

तो, यदि इनपुट nums = [-2, 6, 4, 3, 8], target = 12 जैसा है, तो आउटपुट 5 होगा, क्योंकि ट्रिपलेट्स हैं: [-2,6,4], [-2,6,3], [-2,4,3], [-2,4,8], [-2,3,8]

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

• सूची nums को सॉर्ट करें
• ans := 0
• n := nums का आकार
• i को 0 से n-1 तक की रेंज में लिए, करें
  • k := n - 1
  • j को i + 1 से n-1 तक की रेंज में लिए, करें
    • जब k > j और nums[i] + nums[k] + nums[j] >= target, करें k := k - 1
    • यदि j, k के समान है, तो ब्रेक करें
    • ans := ans + k - j
• ans लौटाएं

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

उदाहरण

class Solution:
    def solve(self, nums, target):
        nums.sort()
        ans = 0
        n = len(nums)
        for i in range(n):
            k = n - 1
            for j in range(i + 1, n):
                while k > j and nums[i] + nums[k] + nums[j] >= target:
                    k -= 1
                if j == k:
                    break
                ans += k - j
        return ans

ob1 = Solution()
nums = [-2, 6, 4, 3, 8]
target = 12
print(ob1.solve(nums, target))

इनपुट

[-2, 6, 4, 3, 8], 12

आउटपुट

5