สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องคืนค่าดัชนีของจำนวนเต็มสองตัว เช่น ถ้าเรารวมเข้าด้วยกัน เราจะไปถึงเป้าหมายเฉพาะที่ได้รับ ในที่นี้ เราจะใช้สมมติฐานหนึ่งข้อ นั่นคือจะมีโซลูชันเฉพาะตัวเดียวในอาร์เรย์เสมอ ดังนั้นจึงไม่มีดัชนีสองชุดสำหรับเป้าหมายเดียวกัน
ตัวอย่างเช่น สมมติว่าอาร์เรย์เป็นเหมือน A =[2, 8, 12, 15] และผลรวมเป้าหมายคือ 20 จากนั้นจะคืนค่าดัชนี 1 และ 2 เป็น A[1] + A[2] =20
เพื่อแก้ปัญหานี้ เราจะวนรอบแต่ละองค์ประกอบของอาร์เรย์ ดังนั้นให้ทำตามขั้นตอนเหล่านี้เพื่อแก้ปัญหานี้
- กำหนดหนึ่งแผนที่เพื่อเก็บผลลัพธ์ที่เรียกว่า res
- สำหรับดัชนี i ในช่วง 0 ถึง n – 1 (โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์)
- ถ้าเป้าหมาย − A[i] มีอยู่ใน res
- return res[target − A[i]] และ i เป็นดัชนี
- มิฉะนั้นให้ใส่ i ลงใน res เป็น res[A[i]] − =i
- ถ้าเป้าหมาย − A[i] มีอยู่ใน res
มาดูการใช้งานกันให้เกิดความเข้าใจกันมากขึ้น
ตัวอย่าง
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
required = {}
for i in range(len(nums)):
if target - nums[i] in required:
return [required[target - nums[i]],i]
else:
required[nums[i]]=i
input_list = [2,8,12,15]
ob1 = Solution()
print(ob1.twoSum(input_list, 20)) อินพุต
input_list = [2,8,12,15] target = 20
ผลลัพธ์
[1, 2]
