Chương trình học Bài 55 trên tổng số 148 · Tốc độ không cần bộ đệm
Tốc độ không cần bộ đệm

Hai con trỏ, không bảng

Vì sao điều này quan trọng "Tìm hai thứ cộng lại bằng X" có một câu trả lời nổi tiếng: đặt mọi thứ vào một tập và tra phần tử đi cặp. Nó nhanh, và nó cần một bản sao của toàn bộ dữ liệu. Khi dữ liệu đã được sắp xếp, bạn gần như không cần bộ nhớ nào.

Một dịch vụ quà tặng bán các gói gồm hai sản phẩm khác nhau với một giá gói cố định. Bảng giá sản phẩm đã được sắp xếp, không có giá trị lặp, và nằm trên một thiết bị nhúng có rất ít bộ nhớ trống. Với một giá gói, bạn cần số cặp sản phẩm có giá cộng lại đúng bằng giá đó.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Đến lượt bạn

Viết count_pairs(tape, target). tape là một Tape các giá nguyên, sắp xếp tăng dần, không có giá trị lặp. Trả về số cặp gồm hai phần tử khác nhau cộng lại đúng bằng target (mỗi cặp tính một lần). Ngân sách: với 20.000 phần tử đọc nhiều nhất 60.000 giá trị, và dùng nhiều nhất 16.000 byte bộ nhớ làm việc trong lúc hàm của bạn chạy (đo bằng tracemalloc; một tập hay list 20.000 giá là hơn 150.000 byte). len(tape) là miễn phí.

Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này

Bài tập này sẽ sớm mở.

Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.