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:
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:
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)
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:
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
YOU MIGHT ALSO LIKE