Two Sum ใน Python

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องคืนค่าดัชนีของสองจำนวนเต็ม ที่ถ้าเราบวกมันเข้าด้วยกัน จะได้เป้าหมายเฉพาะที่กำหนดไว้ ที่นี่เราจะสมมติฐานหนึ่งคือ จะมีคำตอบที่ไม่ซ้ำกันอยู่เสมอในอาร์เรย์ ดังนั้นไม่มีชุดดัชนีสองชุดสำหรับเป้าหมายเดียวกัน

ตัวอย่างเช่น สมมติอาร์เรย์เป็น A = [2, 8, 12, 15] และเป้าหมายผลรวมคือ 20 แล้วจะคืนค่าดัชนี 1 และ 2 เนื่องจาก A[1] + A[2] = 20

วิธีการแก้ปัญหา

เราจะวนลูปผ่านแต่ละองค์ประกอบของอาร์เรย์ ดังนั้นทำตามขั้นตอนเหล่านี้เพื่อแก้ปัญหานี้:

• กำหนดแมพหนึ่งอันเพื่อเก็บผลลัพธ์ชื่อ res
• สำหรับดัชนี i ในช่วง 0 ถึง n - 1 (โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์):
  • ถ้า target - A[i] อยู่ใน res:
    • คืนค่า res[target - A[i]] และ i เป็นดัชนี
  • มิฉะนั้น ใส่ i ลงใน res เป็น res[A[i]] = i

ตัวอย่าง

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]