LeetCode là một nền tảng cung cấp quyền truy cập vào hàng nghìn vấn đề lập trình và giúp người dùng nâng cao kỹ năng của họ cũng như chuẩn bị cho các cuộc phỏng vấn kỹ thuật thường là một phần của quy trình tuyển dụng cho các vị trí Kỹ thuật và Máy học
Trong phần hướng dẫn ngắn ngày hôm nay, chúng ta sẽ khám phá bài toán đầu tiên có tên là Hai Tổng và cố gắng giải nó theo cách tối ưu. Trong các cuộc phỏng vấn kỹ thuật, điều quan trọng không chỉ là tìm ra giải pháp cho một vấn đề cụ thể mà sự phức tạp về thời gian cũng là điều bạn thường được hỏi về
Bài toán hai tổng
Cho một mảng các số nguyên nums và một số nguyên
Input: nums = [3,2,4], target = 66, trả về các chỉ số của hai số sao cho tổng của chúng bằng
Output: [1,2]Input: nums = [3,2,4], target = 66
Output: [1,2]Bạn có thể cho rằng mỗi đầu vào sẽ có chính xác một giải pháp và bạn không thể sử dụng cùng một phần tử hai lần
Bạn có thể trả lời câu trả lời theo thứ tự bất kỳ
ví dụ 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].ví dụ 2
Input: nums = [3,2,4], target = 6
Output: [1,2]ví dụ 3
Input: nums = [3,3], target = 6
Output: [0,1]Hạn chế
Input: nums = [3,2,4], target = 68
Output: [1,2]Input: nums = [3,2,4], target = 69
Output: [1,2]Input: nums = [3,3], target = 60
Output: [0,1]- Chỉ có một câu trả lời hợp lệ tồn tại
Nguồn. LeetCode
không phải như vậy. giải pháp tối ưu
Cách tiếp cận đơn giản nhất sẽ yêu cầu hai vòng lặp lồng nhau trong đó vòng lặp bên ngoài lặp qua tất cả các phần tử của danh sách và vòng lặp bên trong lặp lại từ chỉ mục hiện tại của vòng lặp bên ngoài cho đến cuối danh sách
from typing import Listclass Solution: def twoSum[self, nums: List[int], target: int] -> List[int]:
for i in range[len[nums]]:
for j in range[i, len[nums]]:
if nums[i] + nums[j] == target:
return [i, j]
Độ phức tạp về thời gian của giải pháp trên là O[n²] khá. xấu
Giải bài toán trong O[n]
Vấn đề này sẽ được giải quyết hiệu quả hơn nếu bằng cách nào đó chúng ta có thể lặp lại danh sách các số chỉ một lần. Để làm như vậy, chúng ta có thể tận dụng một từ điển
Trong giải pháp bên dưới, trước tiên chúng tôi tạo một từ điển trống, nơi chúng tôi sẽ lưu trữ giá trị và chỉ mục của từng thành phần danh sách dưới dạng một cặp khóa tương ứng. Sau đó, chúng tôi lặp qua các chỉ số và giá trị của danh sách chứa các số của chúng tôi. Nếu sự khác biệt giữa giá trị mục tiêu và giá trị hiện tại trong danh sách đã được đưa vào làm khóa trong từ điển, thì điều đó có nghĩa là giá trị hiện tại và giá trị được lưu trữ trong từ điển là giải pháp cho vấn đề của chúng ta
Mặt khác, chúng tôi chỉ cần thêm giá trị và chỉ mục dưới dạng cặp khóa-giá trị trong từ điển của mình và tiếp tục lặp lại cho đến khi chúng tôi tìm thấy giải pháp mà mình đang tìm kiếm
from typing import Listclass Solution: def twoSum[self, nums: List[int], target: int] -> List[int]:
values = {}
for idx, value in enumerate[nums]:
if target - value in values:
return [values[target - value], idx]
else:
values[value] = idx
Trong giải pháp trên, chúng tôi lặp lại danh sách các số chỉ một và do đó độ phức tạp về thời gian của thuật toán là O[n], tốt hơn nhiều so với giải pháp đã triển khai trước đó
Suy nghĩ cuối cùng
Trong bài viết ngắn ngày hôm nay, chúng ta đã thảo luận về một số cách tiếp cận xung quanh bài toán Hai Tổng trong LeetCode. Ban đầu, chúng tôi đã tạo ra một giải pháp đơn giản dẫn đến hiệu suất kém, nhưng sau đó chúng tôi đã tận dụng các từ điển Python để triển khai giải pháp với độ phức tạp về thời gian O[n]
Trở thành thành viên và đọc mọi câu chuyện trên Medium. Phí thành viên của bạn hỗ trợ trực tiếp cho tôi và các nhà văn khác mà bạn đọc. Bạn cũng sẽ có toàn quyền truy cập vào mọi câu chuyện trên Phương tiện
Cho một mảng các số nguyên
Input: nums = [3,3], target = 6
Output: [0,1]1 và một số nguyên Input: nums = [3,2,4], target = 6
Output: [1,2]6, trả về các chỉ số của hai số sao cho tổng của chúng bằng Input: nums = [3,2,4], target = 6
Output: [1,2]6Bạn có thể cho rằng mỗi đầu vào sẽ có chính xác một giải pháp và bạn không thể sử dụng cùng một phần tử hai lần
Bạn có thể trả lời câu trả lời theo thứ tự bất kỳ
Hạn chế
- 2 elements from the given array2. Chúng tôi sẽ chỉ gặp phần tử này trước đây chỉ khi chúng tôi đã lưu sự khác biệt của
Input: nums = [3,2,4], target = 66 và phần tử mà khi được thêm vào phần tử hiện tại sẽ tạo ra chính
Output: [1,2]Input: nums = [3,2,4], target = 66. Điều này thật khó hiểu, tôi biết nhưng một khi nó nhấp vào, nó rất rõ ràng
Output: [1,2] - Nếu chúng tôi không có, chúng tôi sẽ tiết kiệm sự khác biệt của
Input: nums = [3,2,4], target = 66 và
Output: [1,2]
2c = a + b where, c => target a and b => elements from the given array - Lặp lại quy trình
Vì chúng tôi cần lưu trữ
c = a + b
where,
c => target
a and b => elements from the given arrayc = a + b
where,
c => target
a and b => elements from the given arrayVì chúng tôi chỉ lặp lại mảng một lần, nên độ phức tạp về thời gian sẽ là O[n]
Vì chúng ta cần một Bản đồ có kích thước của mảng, nên độ phức tạp của không gian sẽ là O[n]
Bây giờ chúng tôi có một cách tiếp cận để giải quyết vấn đề này, hãy viết một số mã -
Java
con trăn
JavaScript
Kotlin
Sự kết luận
Tôi hy vọng bạn thích bài viết này. Ở đây, chúng tôi đã giải quyết vấn đề đầu tiên trên LeetCode trong thời gian O[n] và không gian O[n]