3Sum ใน Python

สมมติว่าเรามีอาร์เรย์ของตัวเลข มันเก็บจำนวนเต็ม n จำนวน มีองค์ประกอบ a, b, c ในอาร์เรย์ เช่น a + b + c =0 ค้นหาแฝดสามที่ไม่ซ้ำกันทั้งหมดในอาร์เรย์ที่ตรงกับสถานการณ์ ดังนั้นหากอาร์เรย์เป็นแบบ [-1,0,1,2,-1,-4] ผลลัพธ์จะเป็น [[-1, 1, 0], [-1, -1, 2]]

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

• จัดเรียงจำนวนอาร์เรย์ และกำหนดความละเอียดของอาร์เรย์
• สำหรับ i ในช่วง 0 ถึงความยาวของ nums – 3
  • ถ้า i> 0 และ nums[i] =nums[i - 1] ให้ข้ามส่วนถัดไปและดำเนินการต่อ
  • l :=i + 1 and r :=length of nums – 1
  • ในขณะที่ l
  • sum :=ผลรวมของ nums[i], nums[l] และ nums[r]
  • ถ้าผลรวม <0 แล้ว l :=l + 1 มิฉะนั้นเมื่อผลรวม> 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

ตัวอย่าง(Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −

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(l<r):
            sum = nums[i] + nums[l] + nums[r]
            if sum<0:
               l+=1
            elif sum >0:
               r-=1
            else:
               result.append([nums[i],nums[l],nums[r]])
               while l<len(nums)-1 and nums[l] == nums[l + 1] : l += 1
               while r>0 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]]