पायथन में 3Sum

मान लीजिए हमारे पास संख्याओं की एक सरणी है। यह n पूर्णांकों को संग्रहीत करता है, सरणी में तीन तत्व a, b, c हैं, जैसे कि a + b + c = 0। सरणी में उन सभी अद्वितीय ट्रिपलेट्स को ढूंढें जो स्थिति को संतुष्ट करते हैं। इसलिए यदि सरणी [-1,0,1,2,-1,-4] जैसी है, तो परिणाम [[-1, 1, 0], [-1, -1, 2]] होगा।

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

• सरणी nums को सॉर्ट करें, और एक सरणी res परिभाषित करें
• i के लिए 0 से nums की लंबाई - 3 तक की रेंज में
  • यदि i > 0 और nums[i] = nums[i - 1], तो अगले भाग को छोड़ें और जारी रखें
  • l := i + 1 और r := nums की लंबाई - 1
  • जब तक l < r
    • sum := nums[i], nums[l] और nums[r] का योग
    • यदि sum < 0, तो l := l + 1, अन्यथा जब sum > 0, तो r := r - 1
    • अन्यथा nums[i], nums[l], nums[r] को res सरणी में डालें
    • जब तक l < nums की लंबाई - 1 और nums[l] = nums[l + 1]
      • l को 1 से बढ़ाएं
    • जब तक r > 0 और nums[r] = nums[r - 1]
      • r को 1 से घटाएं
    • l को 1 से बढ़ाएं और r को 1 से घटाएं
• res लौटाएं

उदाहरण (पायथन)

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

class Solution(object):    def threeSum(self, nums):       nums.sort()       result = []       for i in range(len(nums)-2):          if i> 0 and nums[i] == nums[i-1]:             continue          l = i+1          r = len(nums)-1          while(l0:                r-=1             else:                result.append([nums[i],nums[l],nums[r]])                while l0 and nums[r] == nums[r - 1]: r -= 1                l+=1                r-=1       return result ob1 = Solution() print(ob1.threeSum([-1,0,1,2,-1,-4]))

इनपुट

[-1,0,1,2,-1,-4]

आउटपुट

[[-1,-1,2],[-1,0,1]]