Giải pháp hai tổng leetcode Python

Giải pháp được mã hóa

1   class Solution:
2      def twoSum[self, nums: list[int], target: int] -> list[int]:
3          the_dict = {}
4          for index, num in enumerate[nums]:
5              the_value = target - num
6              if the_value in the_dict:
7                  return[index, the_dict[the_value]]
8              the_dict[num] = index
9 
10   # Time Complexity is O[n]
11   # Space Complexity is O[n]

  

Từng dòng trong Giải pháp mã hóa được giải thích

1. Dòng 1 tạo Lớp của chúng tôi mà chúng tôi đặt tên là Giải pháp, điều này là bắt buộc trong LeetCode
2. Dòng 2 tạo Phương thức của chúng tôi có tên là twoSum, điều này là bắt buộc trong LeetCode
3. Dòng 3 là nơi chúng tôi tạo từ điển, chúng tôi để trống để lưu trữ các giá trị số nguyên làm khóa và giá trị chỉ mục làm giá trị
4. Dòng 4 là nơi chúng ta bắt đầu lặp qua mảng đầu vào mà chúng ta được cung cấp. enumerate là một hàm có sẵn trong Python cho phép chúng ta sử dụng các chỉ số. Trong trường hợp này, chúng ta cần lưu trữ các chỉ số dưới dạng giá trị trong các cặp khóa/giá trị trong từ điển của mình trong khi chúng ta lưu trữ các số nguyên tại chỉ mục đã cho làm khóa trong từ điển
5. Dòng 5 chúng tôi đang lấy mục tiêu và trừ nó khỏi số và lưu trữ nó trong the_value
6. Dòng 6 kiểm tra xem the_value có trong từ điển của chúng ta hay không
7. Trạng thái dòng 7 trả về các chỉ số của chúng tôi vì chúng tôi đã tìm thấy các giá trị của mình
8. Dòng 8 sẽ chạy nếu the_value không được tìm thấy trong từ điển của chúng tôi, những gì nó làm là tạo một khóa mới với num and to store the value index at that new key

Thời gian phức tạp

Vì ký hiệu Big O liên quan đến trường hợp xấu nhất. Chúng ta sẽ có độ phức tạp thời gian là O[n] thời gian tuyến tính. Vì tệ nhất là chúng ta phải duyệt qua toàn bộ mảng để tìm đúng chỉ mục. Và nhờ có từ điển, việc tra cứu đã trở thành hằng số O[1] thời gian

Độ phức tạp không gian

Trong trường hợp xấu nhất, chúng ta sẽ phải duyệt qua toàn bộ mảng và cũng sẽ phải lưu trữ từng số nguyên dưới dạng khóa trong từ điển của chúng ta trong khi chỉ mục của nó sẽ được lưu trữ dưới dạng giá trị trong từ điển của chúng ta. Do đó, chúng ta sẽ có độ phức tạp không gian của không gian tuyến tính O[n]

Trong hướng dẫn này, chúng ta sẽ thực hiện bài toán tổng hai số bằng cách sử dụng mã Python. Đây là vấn đề cơ bản của mảng, và bạn có thể tìm thấy vấn đề này trên Leetcode. Chúng tôi sẽ giải quyết nó bằng một cách tiếp cận khác bằng ngôn ngữ lập trình Python. Hãy hiểu tuyên bố vấn đề

Báo cáo vấn đề

Trong bài toán này, chúng ta cần tìm cặp gồm hai phần tử từ danh sách đã cho có tổng bằng giá trị mục tiêu đã cho. Chúng ta có thể giả sử rằng mảng chỉ có một cặp số nguyên cộng lại thành tổng mục tiêu

Lưu ý - Một danh sách hoặc mảng nhất định phải được sắp xếp tăng dần

Ví dụ 1

đầu ra

Ví dụ - 2

đầu ra

Hãy giải quyết vấn đề này bằng cách sử dụng phương pháp Brute Force

Cách tiếp cận - 1. Cách tiếp cận vũ phu

Cách tiếp cận vũ phu là cách thường được sử dụng để giải quyết vấn đề. Trong cách tiếp cận này, mục tiêu chính của chúng tôi là giải quyết vấn đề, không hiệu quả. Chúng tôi kiểm tra mọi cặp có thể và số lượng các cặp có thể có trong mảng. Chúng tôi sẽ sử dụng hai vòng lặp for, cộng hai giá trị và so sánh giá trị đích. Nếu nó bằng giá trị đích, trả về chỉ số của các cặp số nguyên

thuật toán -

• Chạy vòng lặp đầu tiên để trỏ chỉ mục đầu tiên của giải pháp trong mảng
• Chạy một vòng lặp khác để trỏ chỉ mục thứ hai của giải pháp cho mọi số nguyên đầu tiên
• Nếu cả hai phần tử bằng giá trị đích, hãy trả về giá trị của cả hai chỉ số

Hãy triển khai thuật toán bằng mã Python

Thực hiện bài toán tổng hai

Thí dụ -

đầu ra

Giải trình -

Trong chương trình trên, chúng ta đã tạo lớp TwoSum và khởi tạo hai biến list1 và target. Sau đó, chúng tôi khai báo phương thức solution[] nơi đầu tiên chúng tôi kiểm tra độ dài của danh sách và áp dụng hai vòng lặp for. Vòng lặp for đầu tiên là duy trì chỉ mục đầu tiên và vòng lặp for thứ hai là duy trì chỉ mục thứ hai. Chúng tôi đã kiểm tra tổng của cả hai giá trị;

Ví dụ - 2

đầu ra

Tiếp cận -2. Sử dụng từ điển

đầu ra

Giải trình -

Theo cách tiếp cận này, chúng tôi đã tạo lớp TwoSum và bên trong nó, chúng tôi khai báo phương thức solution[]. Trong phương pháp này, chúng tôi đã khai báo một từ điển để theo dõi tất cả các giá trị được thấy cho đến nay trong giá trị của chỉ mục. Bây giờ, chúng tôi lặp lại danh sách đã cho bằng cách sử dụng kiểu liệt kê. Sau đó, chúng tôi trừ giá trị num khỏi giá trị đích để tìm kiếm cặp của nó. Nếu cặp được tìm thấy, hãy trả về chỉ số của cả hai số. Nếu không, hãy thêm nó vào từ điển của chúng tôi để truy cập trong tương lai

Độ phức tạp thời gian của tổng hai số [Phương pháp tiếp cận vũ phu]

Chúng ta cần sử dụng hai vòng lặp for. Vòng lặp for đầu tiên truy cập n số phần tử và vòng lặp thứ hai truy cập n-1. Do đó, việc kiểm tra khả năng và tổng số cặp là. N*[N-1]/2, độ phức tạp về thời gian sẽ là O[N*N] = N2

Độ phức tạp không gian

0[1]. Chỉ không gian cố định cho biến được sử dụng

Sử dụng từ điển, chỉ cần một vòng lặp for nên độ phức tạp về thời gian sẽ là O[N]

Cách tiếp cận - 3. Sử dụng hai con trỏ

Trong cách tiếp cận này, chúng tôi sẽ sử dụng thuật toán tìm kiếm nhị phân trong đó mảng danh sách đã cho phải được sắp xếp. Chúng tôi cần sửa chỉ mục đầu tiên và sau đó là giá trị bắt buộc để hoàn thành mục tiêu được tìm thấy trong danh sách

Chúng ta sẽ sử dụng hai con trỏ. bên trái và bên phải; . Sau đó, chúng tôi so sánh tổng giá trị của con trỏ với giá trị đích; . Nếu tổng giá trị lớn hơn mục tiêu, chúng tôi giảm con trỏ bên phải. Mặt khác, một số giá trị nhỏ hơn mục tiêu;

Hãy hiểu ví dụ sau

Thí dụ -

đầu ra

Độ phức tạp của thời gian sử dụng hai tổng

Độ phức tạp về thời gian sẽ là O[n] thậm chí trong trường hợp xấu nhất, chúng ta chỉ truy cập tất cả các phần tử trong mảng một lần

Độ phức tạp của không gian

0[1]. Chỉ không gian cố định cho biến được sử dụng

Sử dụng từ điển, chỉ cần một vòng lặp for để độ phức tạp về thời gian sẽ là O[n]

Sự kết luận

Đó là một câu hỏi lập trình cơ bản và thường được hỏi trong cuộc phỏng vấn. Trong hướng dẫn này, chúng tôi đã đề cập đến ba cách tiếp cận để giải bài toán tổng hai. Chúng tôi khuyên bạn nên thực hiện các phương pháp trên một cách độc lập và thực hành các câu hỏi như vậy để bẻ khóa các cuộc phỏng vấn viết mã