Hai tổng (Two Sum) trong Python

Cho mảng số nguyên, tìm chỉ số hai số cộng bằng target. Giả sử luôn có duy nhất một giải. Ví dụ: [2,8,12,15], target=20 → [1,2].

Giải pháp

Hash map lưu giá trị → chỉ số:

• Duyệt i: nếu target-nums[i] trong map → trả về [map[target-nums[i]], i].
• Ngược lại lưu nums[i]:i vào map.

Ví dụ

Triển khai Python:

class Solution(object): 
    def twoSum(self, nums, target): 
        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))

Đầu vào

input_list = [2,8,12,15] target = 20

Đầu ra

[1, 2]