สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และองค์ประกอบใน nums จะถูกจัดเรียงตามลำดับจากน้อยไปมาก เรายังมีค่า k อีกค่าหนึ่ง เราต้องตรวจสอบว่าสององค์ประกอบที่นำมาจากรายการนั้นรวมกันเป็น k หรือไม่ ตัวเลขสามารถเป็นลบหรือ 0 ได้เช่นกัน เราต้องแก้ปัญหานี้โดยใช้พื้นที่ในปริมาณคงที่
ดังนั้น หากอินพุตเป็น nums =[-8, -3, 2, 7, 9] k =4 ผลลัพธ์จะเป็น True เพราะถ้าเราเอา 7 และ -3 ผลรวมจะเป็น 7 + (- 3) =4 ซึ่งเท่ากับ k
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ผม :=0
- j :=ขนาดของ nums - 1
- ในขณะที่ฉัน
- cur_sum :=nums[i] + nums[j]
- ถ้า cur_sum เหมือนกับ k แล้ว
- คืนค่า True
- มิฉะนั้น เมื่อ cur_sum
- ผม :=ผม + 1
- j :=j - 1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums, k): i = 0 j = len(nums) - 1 while i < j: cur_sum = nums[i] + nums[j] if cur_sum == k: return True elif cur_sum < k: i += 1 else: j -= 1 return False nums = [-8, -3, 2, 7, 9] k = 4 print(solve(nums, k))
อินพุต
[-8, -3, 2, 7, 9], 4
ผลลัพธ์
True
