[300 Bài Code Thiếu Nhi] Two Sum – Python

Mô tả bài toán

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

Giải pháp

Giải pháp của mình

Một giải pháp đơn giản cho vấn đề này là kiểm tra mọi cặp có thể có trong mảng đã cho.

Đối với mảng đầu vào nums, chúng ta cần thực hiện các bước sau:

1. Chạy hai vòng lặp và kiểm tra mọi kết hợp trong mảng đã cho.
2. Cố định vòng lặp bên ngoài tại một chỉ mục cụ thể và di chuyển vòng lặp bên trong để lấy tất cả các cặp có thể có. Vòng ngoài chạy từ i = 0 đến i = n-2 và vòng trong chạy từ j = i + 1 đến j = n-1 (n là kích thước của mảng nums).
3. Trong mỗi lần lặp lại của vòng lặp bên trong, hãy kiểm tra xem các số được biểu thị bằng chỉ số vòng lặp bên ngoài và bên trong có cộng lại với tổng mục tiêu không.
4. Nếu nums[outerLoopIndex] + nums[innerLoopIndex] bằng target, thì trả về {outerLoopIndex, innerLoopIndex}. Nếu không thì tiếp tục kiểm tra mảng tiếp theo.
5. Lặp lại các bước trên cho đến khi bạn tìm thấy một kết quả cho mục tiêu đã cho.

Code:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        i = 0
        n = len(nums)
        while (i < n-1):
            j = i+1
            while (j < n):
                if(nums[i] + nums[j] == target):
                    return [i, j]
                j+=1
            i+=1
        return []
        

Trường hợp xấu nhất sẽ xảy ra khi kết hợp bắt buộc là kết hợp cuối cùng được các vòng lặp kiểm tra.

Độ phức tạp:

Time Complexity: O(n^2)
Space Complexity: O(1)

Giải pháp khác

Sau một thời gian tra cứu thì mình đã tìm ra một thuật toán khác tối ưu hơn, nó đã khiến mình mất khá nhiều thời gian để hiểu.

Ý tưởng là sử dụng hashmap để lưu trữ các chỉ số của các phần tử đã được duyệt qua. Hashmap “key” là giá trị trong mảng đầu vào nums đã cho (Bạn thêm mã này vào hashmap khi bạn truy cập từng phần tử). Hashmap “value” là chỉ số của giá trị trong mảng nums được đại diện bởi khóa hashmap.

Chúng ta cần thực hiện các bước sau:

1. Tạo một hashmap chấp nhận kiểu dữ liệu số nguyên làm khóa và giá trị.
2. Lặp lại từng phần tử trong mảng đã cho bắt đầu từ phần tử đầu tiên.
3. Trong mỗi lần lặp, hãy kiểm tra xem required number (required number = số mục tiêu – số hiện tại) có trong bản đồ băm hay không.
4. Nếu có thì trả về {chỉ số của required number, chỉ số của số hiện tại}
5. Nếu không, hãy thêm số hiện tại làm key và chỉ mục của nó làm value dưới dạng giá trị vào bản đồ băm. Lặp lại điều này cho đến khi bạn tìm thấy kết quả.

Ví dụ:

Nếu bạn được cung cấp 1 mảng đầu vào như hình dưới và target = 24

Đặt currIdx là biến đại diện cho phần tử hiện tại đang được xử lý và idxMap là chỉ mục của hashmap. Các ô được đánh dấu màu cam cho biết phần tử mảng hiện đang được xử lý.

Lúc đầu, currIdx = 0 và idxMap trống như trong hình đầu tiên bên dưới. Tiếp theo, chúng tôi kiểm tra xem required number = target – số hiện tại có trong idxMap hay không.

Required number = 24 – 7 = 17 không có trong hashmap, vì vậy ta thêm 7 làm khóa idxMap và 0 làm giá trị idxMap (0 là chỉ số của 7 trong mảng đầu vào nums) như trong hình 2 bên dưới.

Tiếp theo, chúng ta chuyển sang phần tử thứ hai trong mảng bằng cách tăng chỉ số hiện tại. Vì vậy, currIdx = 1 trỏ đến phần tử 2 trong mảng.

Một lần nữa, chúng tôi kiểm tra xem required number có trong idxMap hay không, required number = 24 – 2 = 22 không có trong idxMap, vì vậy ta thêm vào 2 vào idxMap cùng với chỉ mục 1 của nó.

Chỉ số hiện tại tăng lên, currIdx = 2, là phần tử 13 trong mảng đầu vào. Một lần nữa required number = 24 – 13 = 11 không có trong idxMap. Thêm {13: 2} vào idxMap. Tương tự được thể hiện trong sơ đồ dưới đây.

idxMap hiện chứa 3 phần tử 7, 2 và 13 cùng với các chỉ mục của chúng. Một lần nữa chúng ta tăng currIdx, currIdx = 3 là phần tử 11 trong mảng.

Bây giờ required number = 24 – 11 = 13 có trong idxMap (được hiển thị bằng ô được đánh dấu màu xanh lá cây trong hình thứ hai bên dưới). Điều đó có nghĩa là chúng ta đã tìm thấy cặp có tổng mục tiêu là 24, tức là (11, 13). Do đó, chúng tôi trả về chỉ số 11 và 13 như kết quả. Chỉ số của 11 là currIdx = 3 và chỉ số của 13 có thể được tìm thấy từ hashmap là 2, do đó chúng ta trả về (3, 2) hoặc (2, 3).

Code:

class Solution:
   def twoSum(self, nums, target):
       seen = {}
       for i, value in enumerate(nums):
           remaining = target - nums[i]
           
           if remaining in seen:
               return [i, seen[remaining]]
            
           seen[value] = i 

Độ phức tạp:

Time Complexity: O(n)
Space Complexity: O(n)

Thời gian chạy của giải pháp này là O (n) vì chúng ta sẽ phải xem qua tất cả các phần tử của mảng trong trường hợp xấu nhất.

Ngoài ra, không gian phụ cần thiết là O (n) vì chúng ta lưu trữ các phần tử của mảng trong hashmap và trong trường hợp xấu nhất, chúng ta sẽ lưu trữ tất cả các giá trị trong mảng đã cho trong hashmap.

You need to login in order to like this post: click here