สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และค่าเป้าหมายอื่น เราต้องหาจำนวนสามเท่า (i
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[−2, 6, 4, 3, 8], target =12 ผลลัพธ์จะเป็น 5 เนื่องจากแฝดสามคือ:[-2,6,4], [-2 ,6,3], [−2,4,3], [-2,4,8], [−2,3,8]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เรียงเลขรายการ
-
ตอบ :=0
-
n :=ขนาดของ nums
-
สำหรับฉันอยู่ในช่วง 0 ถึง n-1 ทำ
-
k :=n − 1
-
สำหรับ j ในช่วง i + 1 ถึง n-1 ให้ทำ
-
ในขณะที่ k> j และ nums[i] + nums[k] + nums[j]>=เป้าหมาย ทำ
-
k :=k − 1
-
-
ถ้า j เหมือนกับ k แล้ว
-
-
ans :=ans + k − j
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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