Leetcode: Tổng hợp hai cách tiếp cận trực quan

Hãy tưởng tượng bạn là chủ sở hữu đáng tự hào của một cửa hàng lưu niệm bên trong Khách sạn Spot-On Change. Khi đóng máy tính tiền, bạn nhận thấy có dư 8 euro. Có vẻ như một vị khách đã không nhận được số tiền lẻ chính xác. Điều này có thể làm hoen ố danh tiếng của khách sạn. Để tránh điều này, bạn quyết định giải quyết bí ẩn về sự thay đổi không chính xác. Khi mở hệ thống tiền mặt của cửa hàng, bạn phát hiện ra lỗi xảy ra trên hai tài khoản khác nhau!

Bạn nghĩ ra một kế hoạch: đến thăm từng phòng và hỏi khách xem họ đã nhận được tiền lẻ nào trong cửa hàng cho đến khi bạn phát hiện ra hai người có hóa đơn sai. Đến tầng một, một vị khách báo nhận được 4 euro tiền lẻ. Bạn tính rằng cần tìm một số mà khi cộng vào 4 euro sẽ ra kết quả là 8. Lên tầng hai, số tiền thối lại của khách là 5 euro. 4 + 5 kết quả là 9, nên không thể là tầng này được… Tầng năm, tầng sáu… Tầng mười, KHÔNG, KHÔNG, KHÔNG!

Vì bạn không tìm thấy giá trị trong lần thử đầu tiên nên bạn đi xuống tầng hai và bắt đầu hỏi lại tất cả khách về sự thay đổi của họ để bạn có thể so sánh nó với giá trị ở tầng bắt đầu tiếp theo, mệt quá, phải không? Nó? Trong khoa học máy tính, phương pháp tìm kiếm này được gọi là brute Force, một phương pháp tìm kiếm cực kỳ chậm, hoạt động bằng cách so sánh một mục với các mục sau trong mảng.

Việc này tiêu tốn rất nhiều thời gian và không hiệu quả, hãy tưởng tượng việc đi lên xuống tất cả các tầng của Khách sạn Spot-On Change nhiều lần! Điều này không thực tế đối với bạn và cũng không thực tế đối với máy tính.

Nếu bạn tò mò về cách thức di chuyển lên xuống các tầng trong một chương trình phần mềm, thì nó sẽ trông như thế này trong JavaScript:

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

Sau khi bình tĩnh đánh giá tình hình, bạn nhận ra rằng có một cách hiệu quả hơn để tìm ra hai vị khách đã đổi sai.

Bạn tinh chỉnh trực giác toán học ban đầu của mình rằng 9 euro bằng x + y. Áp dụng một chút phép tính, bạn nhận ra rằng: x + y = 9 cũng giống như nói y = 9 — x, và điều đó tạo nên sự khác biệt khi tăng hiệu quả tìm kiếm của bạn.

Một điều nữa đã thay đổi trong chiến lược của bạn là bây giờ bạn sẽ lấy một cuốn sổ ghi lại những giá trị mà khách nói với bạn, để bạn không phải hỏi khách cùng một giá trị hai lần và bạn không phải bỏ ra chi phí. ngày lên xuống cầu thang. (Thật là một khoảng thời gian khủng khiếp khi thang máy bị hỏng!).

Với các công cụ mới trong tay, bạn đi lên tầng một, nơi một vị khách thông báo với bạn rằng họ có 5 euro tiền lẻ. Bạn ghi giá trị này là {5: 0}, biểu thị giá trị 5 ở vị trí 0. Thay x bằng 5 trong phương trình, bạn tính y = 8–5, dẫn đến y = 3. Vì sổ ghi chú của bạn vẫn trống nên bạn không Không ghi số 3, đây sẽ là số bổ sung cho 5 để đạt kết quả 8. Sau đó, bạn viết số 5 vào sổ ghi chú của mình (hãy nhớ luôn ghi số đã được xác minh vào thời điểm đó chứ không phải số bù của nó; bạn sẽ chỉ sử dụng phần bù để so sánh nó với số đích mà bạn đã viết ra). Bạn tiến tới vị khách thứ hai, người này đề cập đến việc nhận lại 2 euro tiền lẻ. Áp dụng lại công thức: y = 8–2 => y = 6, bạn kiểm tra bản ghi của mình, trong đó bạn không tìm thấy số 6 nào. Do đó, bạn thêm 2 vào bản ghi của mình, hiện có dạng {5: 0, 2: 1}. Tiếp tục tìm kiếm, vị khách tiếp theo báo cáo nhận được 3 euro tiền lẻ. Bạn tính lại: y = 8–3 => y = 5. Bingo! Bạn có số 5 được ghi vào notepad của bạn! Khách ở tầng 0 sẽ bổ sung cho khách ở tầng 2! Cách tiếp cận này được gọi là bảng băm, nhanh hơn và hiệu quả hơn nhiều cho cả bạn và máy tính. Trong JavaScript, điều này sẽ được triển khai như sau:

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Đây là một vấn đề dễ dàng từ Leetcode và chỉ trở nên dễ dàng sau khi bạn hiểu các khái niệm đằng sau nó. Tôi khuyên bạn nên cố gắng tự mình giải quyết vấn đề và dành chút thời gian cố gắng xây dựng trực giác đằng sau nó, tạo ra sự tương tự của riêng bạn, xem xét và thử viết mã giả trước khi chuyển sang giải pháp.

Tôi hy vọng sự tương tự của tôi đã giúp bạn hiểu rõ hơn các khái niệm đằng sau thử thách tổng hai.

Hẹn gặp lại lần sau!