Làm thế nào để bạn giải quyết vấn đề hai tổng LeetCode?
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 Show 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
ví dụ 1 Input: nums = [2,7,11,15], target = 9 ví dụ 2 Input: nums = [3,2,4], target = 6 ví dụ 3 Input: nums = [3,3], target = 6 Hạn chế
không phải như vậy. giải pháp tối ưuCá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]: Độ 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]: 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ùngTrong 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 1 và một số nguyên Input: nums = [3,2,4], target = 6 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 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ế
Phân tíchVì vậy, chúng ta phải tìm hai số trong số tất cả các số trong một mảng sao cho khi chúng được thêm vào, chúng sẽ cho chúng ta số thứ ba bằng với Input: nums = [3,2,4], target = 6 6cho e. g. ,
Nói một cách đơn giản hơn, chúng ta cần tìm -
Ngoài ra, các ràng buộc đã cho cho thấy rằng chỉ có MỘT câu trả lời hợp lệ cùng với phạm vi của các phần tử trong mảng và mục tiêu Cách tiếp cậnSau khi chúng tôi đã phân tích vấn đề của mình, giờ là lúc nghĩ về giải pháp Cách tiếp cận số 1Giải pháp đầu tiên xuất hiện trong đầu là -
Khá đơn giản nhỉ 😉? Giả sử mảng có Input: nums = [3,3], target = 6 5 phần tử thì -
Nếu chúng ta đơn giản hóa biểu thức trên, chúng ta sẽ nhận được - n * (n - 1)/2 = n2 - 2n ≈ n2 Do đó, độ phức tạp thời gian của chúng ta sẽ là - O(n2) Vì chúng tôi không sử dụng bất kỳ cấu trúc dữ liệu bổ sung nào nên độ phức tạp về không gian của chúng tôi sẽ là O(1) Cách tiếp cận này đơn giản và trực quan nhưng mất thời gian bậc hai, điều này không tốt cho đầu vào lớn. Hãy xem liệu chúng ta có cách tiếp cận hiệu quả nào để giải quyết vấn đề này không. Trên thực tế, chúng tôi làm 😄 Cách tiếp cận #2Trong cách tiếp cận trước đó, chúng tôi đã làm những gì tự nhiên đến với chúng tôi. Nhưng chúng ta hãy cố gắng suy nghĩ thấu đáo vấn đề này. Hừm… 🤔 Khi chúng tôi đang phân tích vấn đề, chúng tôi bắt gặp phương trình sau nhưng chúng ta có thể viết phương trình trên là - Tất nhiên chúng ta có thể. Rốt cuộc chúng ta là những nhà toán học 😁 Lợi ích của việc viết phương trình này là bây giờ chúng ta có thể lặp qua mảng chỉ một lần và tính toán sự khác biệt của Input: nums = [3,3], target = 6 6 và Input: nums = [3,3], target = 6 7 và tìm 0. Ý tưởng là như sau -
Vì chúng tôi cần lưu trữ 7 của mình, nên chúng tôi cần một cấu trúc dữ liệu có thể lưu trữ 7 và chỉ mục tương ứng của nó. Vậy theo bạn, cấu trúc dữ liệu nào có thể giúp ích cho chúng ta? Vì 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ã - Javacon trănJavaScriptKotlinSự kết luậnTô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) Bài toán 2 tổng là gì?Bài toán hai tổng là gì? . Lưu ý rằng bạn không thể sử dụng cùng một phần tử trong mảng hai lần, nhưng bạn có thể cho rằng sẽ chỉ có một giải pháp cho mỗi trường hợp thử nghiệm. Given an array of integers, return indices of the two numbers such that they add up to a specific target. Note that you cannot use the same element in the array twice, but you can assume that there will only be one solution for each test case.
độ phức tạp thời gian của hai tổng là gì?Độ phức tạp về thời gian. O ( n 2 ) O(n^2) O(n2) . Đối với mỗi phần tử, chúng tôi cố gắng tìm phần bù của nó bằng cách lặp qua phần còn lại của mảng, mất O ( n ) O(n) O(n) thời gian. Do đó, độ phức tạp thời gian là O ( n 2 ) O(n^2) O(n2). Độ phức tạp của không gian. O ( 1 ) O(1) O(1).
Bài toán hai tổng trong Java là gì?Tổng quan. Hai Tổng là một bài toán lập trình trong đó bạn được cung cấp một mảng và một giá trị đích và bạn phải tìm các chỉ số của các phần tử trong mảng có tổng bằng giá trị đích. |