Bỏ qua

Mảng và Băm

Mảng và bảng băm là hai cấu trúc dữ liệu căn bản nhất trong lập trình. Tệp này trình bày cách chúng hoạt động bên trong, sau đó xây dựng các mẫu giải quyết bài toán chủ chốt: hai con trỏ, cửa sổ trượt, tổng tiền tố, và tra cứu dựa trên băm, thông qua các bài toán tăng dần độ khó, kèm theo các cạm bẫy thường gặp ở mỗi bước.

  • Nếu bạn hiểu sâu về mảng và bản băm, bạn có thể giải khoảng 40% mọi bài toán phỏng vấn lập trình. Hai cấu trúc này xuất hiện ở khắp mọi nơi vì chúng cung cấp hai thứ mà thuật toán cần nhất: truy cập nhanh theo chỉ số (mảng) và tra cứu nhanh theo khóa (bản băm).

  • Tệp này dạy các mẫu, không phải lời giải. Mục tiêu là khi bạn gặp một bài toán mới, bạn nhận ra mẫu nào áp dụng và tại sao, thay vì cố nhớ một lời giải thuộc lòng.

Mảng (Arrays)

  • Một mảng (array) là một khối bộ nhớ liên tiếp, nơi các phần tử được lưu ở các độ lệch cố định. Truy cập phần tử \(i\) tốn \(O(1)\) vì địa chỉ đơn giản là base + i * element_size. Đây là cách truy cập dữ liệu nhanh nhất có thể, và đó là lý do mảng là lựa chọn mặc định.

  • Mảng động (dynamic arrays) (kiểu list của Python, ArrayList của Java, vector của C++) tự động mở rộng khi đầy. Chiến thuật là nhân đôi phân bổ (amortised doubling): khi mảng đầy, cấp phát một mảng mới có kích thước gấp đôi và sao chép mọi thứ sang. Việc sao chép tốn \(O(n)\), nhưng nó hiếm khi xảy ra (mỗi \(n\) lần chèn) nên chi phí phân bổ cho mỗi lần chèn là \(O(1)\).

  • Tính định xứ bộ nhớ đệm (cache locality) là lý do mảng nhanh trong thực tế, không chỉ lý thuyết. Vì các phần tử lưu liên tiếp, truy cập một phần tử sẽ nạp các phần tử lân cận vào bộ nhớ đệm CPU (chương 13). Duyệt qua một mảng thân thiện với bộ nhớ đệm; còn đi theo các con trỏ trong danh sách liên kết thì không. Sự khác biệt hệ số hằng này có thể là 10-100 lần trong thực tế.

Thao tác Mảng Mảng động
Truy cập theo chỉ số \(O(1)\) \(O(1)\)
Thêm vào cuối n/a \(O(1)\) phân bổ
Chèn tại vị trí \(i\) \(O(n)\) \(O(n)\)
Xóa tại vị trí \(i\) \(O(n)\) \(O(n)\)
Tìm kiếm (chưa sắp xếp) \(O(n)\) \(O(n)\)
  • Cạm bẫy: chèn hoặc xóa ở giữa một mảng là \(O(n)\) vì mọi phần tử phía sau phải được dịch chuyển. Nếu bạn cần chèn giữa thường xuyên, hãy cân nhắc danh sách liên kết hoặc một cách tiếp cận hoàn toàn khác.

Chuỗi (Strings)

  • Một chuỗi (string) là một mảng các ký tự. Trong Python, chuỗi là bất biến (immutable): mỗi lần nối chuỗi tạo ra một chuỗi mới. Xây dựng một chuỗi từng ký tự trong một vòng lặp là \(O(n^2)\) vì mỗi lần nối sao chép toàn bộ chuỗi hiện tại.
# TỆ: O(n^2) nối chuỗi
s = ""
for c in characters:
    s += c  # sao chép toàn bộ chuỗi mỗi lần

# TỐT: O(n) dùng danh sách rồi join
parts = []
for c in characters:
    parts.append(c)
s = "".join(parts)

  • Cạm bẫy: trong Python, s += c trong một vòng lặp là một trong những lỗi hiệu năng phổ biến nhất. Luôn thu thập vào một danh sách rồi dùng .join().

  • Mã hóa (Encoding): ASCII dùng 7 bit (128 ký tự). UTF-8 có độ dài thay đổi: ký tự ASCII dùng 1 byte, ký tự có dấu dùng 2, ký tự Trung/Nhật dùng 3, emoji dùng 4. Khi một bài toán nói "chữ cái tiếng Anh viết thường", kích thước bảng chữ cái là 26, nghĩa là bạn có thể dùng một mảng có kích thước cố định thay vì bản băm.

Bảng băm (Hash Tables)

  • Một bảng băm (hash table) ánh xạ khóa sang giá trị với tra cứu, chèn, xóa trung bình \(O(1)\). Nó hoạt động bằng cách tính một hàm băm (hash function) \(h(key)\) chuyển đổi khóa thành một chỉ số mảng.

  • Hàm băm phải: xác định (deterministic) (cùng khóa luôn cho cùng một mã băm), đều (uniform) (phân bố khóa đều khắp các bucket), và nhanh để tính.

  • Xung đột (Collisions) xảy ra khi hai khóa khác nhau băm về cùng một chỉ số. Hai chiến thuật chính:

    • Chaining (nối chuỗi): mỗi bucket lưu một danh sách liên kết các cặp khóa-giá trị. Khi xung đột, thêm vào cuối danh sách. Trường hợp xấu nhất (mọi khóa băm về cùng một bucket): \(O(n)\). Trung bình với một hàm băm tốt: \(O(1)\).

    • Open addressing (địa chỉ mở): khi xung đột, dò tìm (probe) slot trống tiếp theo. Linear probing kiểm tra slot kế tiếp, rồi kế tiếp, v.v. Nó thân thiện với bộ nhớ đệm nhưng chịu cảnh tụ cụm (clustering) (các chuỗi slot chiếm dụng dài). Robin Hood hashing giảm phương sai bằng cách dịch chuyển các mục "gần nhà hơn".

  • Hệ số tải (load factor) \(\alpha = n / m\) (số mục / số bucket) quyết định hiệu năng. Khi \(\alpha\) vượt một ngưỡng (thường 0.75), bảng băm lại (rehashes): cấp phát một bảng lớn hơn và chèn lại mọi phần tử. Việc này tốn \(O(n)\) nhưng ít khi xảy ra.

  • Bản băm (hash maps) (dict trong Python, HashMap trong Java) lưu các cặp khóa-giá trị. Tập băm (hash sets) (set trong Python, HashSet trong Java) chỉ lưu khóa (dùng để kiểm tra thành viên nhanh).

Thao tác Trung bình Trường hợp xấu nhất
Tra cứu \(O(1)\) \(O(n)\)
Chèn \(O(1)\) \(O(n)\)
Xóa \(O(1)\) \(O(n)\)

  • Bộ lọc Bloom (Bloom filters) là các tập hợp xác suất tiết kiệm không gian. Chúng có thể nói với bạn "chắc chắn không có trong tập" hoặc "có thể có trong tập" (với tỷ lệ dương tính giả có thể điều chỉnh). Chúng dùng \(k\) hàm băm và một mảng bit. Được dùng trong cơ sở dữ liệu (tránh đọc đĩa cho các khóa vắng mặt), bộ nhớ đệm web, và công cụ kiểm tra chính tả.

  • Khi nào dùng bản băm: bất cứ khi nào bạn cần trả lời "tôi đã thấy cái này trước đây chưa?" hoặc "số đếm/chỉ số/giá trị liên kết với khóa này là gì?" trong \(O(1)\). Nếu bạn đang làm các quét tuyến tính lặp đi lặp lại để tìm thứ gì đó, một bản băm chắc chắn sẽ làm nó nhanh hơn.

Mẫu: Tra cứu Bản băm (Hash Map Lookups)

  • Mẫu cơ bản nhất: dùng bản băm để thay thế các quét \(O(n)\) bằng các tra cứu \(O(1)\).

Dễ: Two Sum

  • Bài toán: cho một mảng số nguyên và một giá trị mục tiêu, trả về chỉ số của hai số cộng lại bằng mục tiêu.

  • Vét cạn \(O(n^2)\): kiểm tra mọi cặp.

  • Cái nhìn sâu về mẫu: với mỗi số num, bạn cần target - num tồn tại ở đâu đó trong mảng. Thay vì quét mảng để tìm nó, hãy lưu các số đã thấy trước đó vào một bản băm.

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

  • Tại sao cách này hoạt động: một lượt qua mảng. Với mỗi phần tử, tra cứu bản băm là \(O(1)\). Tổng: \(O(n)\) thời gian, \(O(n)\) không gian.

  • Cạm bẫy: đừng thêm số hiện tại vào bản băm trước khi kiểm tra phần bù, nếu không bạn có thể khớp một phần tử với chính nó. Thứ tự trong code trên là đúng: kiểm tra trước, rồi chèn.

Trung bình: Gom nhóm Anagram

  • Bài toán: cho một danh sách các chuỗi, gom các anagram lại với nhau. ("eat", "tea", "ate") là một nhóm.

  • Cái nhìn sâu về mẫu: các anagram có cùng các ký tự theo thứ tự khác nhau. Nếu bạn sắp xếp mỗi chuỗi, các anagram tạo ra cùng một khóa đã sắp xếp. Dùng khóa đã sắp xếp đó làm khóa bản băm.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # hoặc dùng tuple đếm tần suất ký tự
        groups[key].append(s)
    return list(groups.values())
  • Tối ưu hóa: sắp xếp mỗi chuỗi tốn \(O(k \log k)\) với \(k\) là độ dài chuỗi. Để có khóa nhanh hơn, hãy đếm tần suất ký tự và dùng tuple đếm làm khóa:
def group_anagrams_fast(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

  • Đây là \(O(k)\) mỗi chuỗi thay vì \(O(k \log k)\). Tuple đếm tần suất ký tự là một dạng chuẩn tắc (canonical form): một biểu diễn giống nhau cho mọi thành viên của một nhóm.

  • Cạm bẫy: trong Python, danh sách không thể băm (không thể làm khóa dict). Bạn phải chuyển sang tuple. Điều này làm nhiều người vấp khi họ thử groups[count].append(s).

Khó: Dãy liên tiếp Dài nhất

  • Bài toán: cho một mảng chưa sắp xếp, tìm độ dài của dãy liên tiếp dài nhất (ví dụ, [100, 4, 200, 1, 3, 2] → 4, vì [1, 2, 3, 4]).

  • Vét cạn \(O(n \log n)\): sắp xếp mảng, rồi quét tìm các đoạn liên tiếp.

  • Cái nhìn sâu về mẫu: đưa mọi số vào một tập băm để tra cứu \(O(1)\). Với mỗi số, kiểm tra xem nó có phải là đầu của một dãy (nghĩa là num - 1 không có trong tập) hay không. Nếu có, đếm dãy kéo dài bao xa.

def longest_consecutive(nums):
    num_set = set(nums)
    best = 0

    for num in num_set:
        # chỉ bắt đầu đếm từ đầu của một dãy
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            best = max(best, length)

    return best

  • Tại sao \(O(n)\): vòng lặp while bên trong chạy nhiều nhất \(n\) lần tổng cộng qua mọi lần lặp (mỗi số được thăm nhiều nhất hai lần: một lần trong vòng lặp ngoài, một lần trong một phần mở rộng while). Câu guard if num - 1 not in num_set đảm bảo ta chỉ bắt đầu đếm từ đầu các dãy.

  • Cạm bẫy: thiếu kiểm tra if num - 1 not in num_set, bạn sẽ bắt đầu đếm từ mọi phần tử, khiến nó thành \(O(n^2)\) trong trường hợp xấu nhất (ví dụ, [1, 2, 3, ..., n] sẽ quét toàn bộ dãy từ mỗi điểm bắt đầu).

Mẫu: Hai con trỏ (Two Pointers)

  • Mẫu hai con trỏ dùng hai chỉ số di chuyển qua mảng, thường từ hai đầu đối diện hoặc từ cùng một đầu với các tốc độ khác nhau. Nó hoạt động khi mảng đã sắp xếp hoặc khi bạn cần so sánh các cặp.

  • Khi nào dùng: bài toán liên quan đến các cặp, mảng con, hoặc phân hoạch, và mảng đã sắp xếp (hoặc có thể sắp xếp mà không làm mất thông tin cần thiết).

Dễ: Palindrome hợp lệ

  • Bài toán: xác định một chuỗi có phải là palindrome hay không, chỉ xét các ký tự alphanumeric và bỏ qua hoa/thường.

  • Mẫu: một con trỏ ở đầu, một ở cuối. Di chuyển chúng vào trong, so sánh các ký tự.

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        # bỏ qua các ký tự không phải alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True
  • Cạm bẫy: quên kiểm tra left < right bên trong các vòng lặp while lồng. Thiếu nó, con trỏ có thể đi ra ngoài giới hạn trên các chuỗi như "!!!" (toàn ký tự không phải alphanumeric).

Trung bình: Three Sum

  • Bài toán: tìm mọi bộ ba (triplet) không trùng lặp trong mảng có tổng bằng không.

  • Mẫu: sắp xếp mảng. Cố định một phần tử, rồi dùng hai con trỏ trên phần còn lại để tìm các cặp có tổng bằng phủ định của phần tử cố định.

def three_sum(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # bỏ qua các phần tử cố định trùng lặp
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1
        target = -nums[i]

        while left < right:
            total = nums[left] + nums[right]
            if total < target:
                left += 1
            elif total > target:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # bỏ qua các phần tử trùng lặp
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

  • Tại sao cách này hoạt động: sắp xếp là \(O(n \log n)\). Với mỗi phần tử cố định, quét hai con trỏ là \(O(n)\). Tổng: \(O(n^2)\), là tối ưu cho bài toán này (bạn phải xét mọi cặp).

  • Cạm bẫy: xử lý trùng lặp là phần khó nhất. Thiếu logic bỏ qua trùng lặp (cả cho phần tử cố định và cho kết quả hai con trỏ), bạn sẽ trả về các bộ ba trùng lặp. Dòng if i > 0 and nums[i] == nums[i-1]: continue là then chốt.

Khó: Giữ nước mưa (Trapping Rain Water)

  • Bài toán: cho một bản đồ độ cao (mảng các số nguyên không âm), tính lượng nước có thể giữ lại sau mưa.

  • Cái nhìn sâu về mẫu: với mỗi vị trí, mức nước được xác định bởi cực tiểu của độ cao lớn nhất bên trái và độ cao lớn nhất bên phải, trừ đi độ cao hiện tại. Hai con trỏ từ hai đầu theo dõi các cực đại đang chạy này.

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

  • Tại sao cách này hoạt động: hiểu biết then chốt là nếu height[left] < height[right], nước tại vị trí left được giới hạn bởi left_max (ta biết có một thanh cao hơn ở bên phải, nên bên phải không thể là điểm thắt nghẹn). Ta xử lý bên ngắn hơn, được đảm bảo bên kia có một thanh cao hơn.

  • Cạm bẫy: nhiều người cố tính trước các mảng left_max[i] và right_max[i] (cách này hoạt động nhưng dùng \(O(n)\) không gian). Cách hai con trỏ đạt \(O(1)\) không gian. Cũng vậy, nhầm >= với > trong các cập nhật cực đại có thể gây lệch một đơn vị trong tính toán nước.

Mẫu: Cửa sổ trượt (Sliding Window)

  • Mẫu cửa sổ trượt duy trì một cửa sổ (mảng con liên tiếp) mở rộng và thu hẹp khi bạn lặp. Nó hoạt động cho các bài toán hỏi về các mảng con hoặc chuỗi con thỏa mãn một điều kiện nào đó.

  • Khi nào dùng: bài toán yêu cầu mảng con hoặc chuỗi con dài nhất/ngắn nhất thỏa mãn một ràng buộc, và việc mở rộng/thu hẹp cửa sổ là đơn điệu (thêm phần tử chỉ làm ràng buộc khó/dễ thỏa mãn hơn, không phải cả hai).

  • Khuôn mẫu (Template):

def sliding_window(arr):
    left = 0
    state = ...  # trạng thái cửa sổ (số đếm, tổng, v.v.)
    best = ...

    for right in range(len(arr)):
        # mở rộng: thêm arr[right] vào trạng thái cửa sổ
        update_state(state, arr[right])

        # thu hẹp: co lại từ bên trái trong khi ràng buộc bị vi phạm
        while constraint_violated(state):
            remove_from_state(state, arr[left])
            left += 1

        # cập nhật đáp án
        best = max(best, right - left + 1)  # hoặc min, tùy bài toán

    return best

Dễ: Thời điểm Tốt nhất để Mua và Bán Cổ phiếu

  • Bài toán: cho giá hàng ngày, tìm lợi nhuận lớn nhất từ một lần mua và một lần bán (mua trước bán sau).

  • Mẫu: theo dõi giá thấp nhất đã thấy tính đến nay (biên trái của cửa sổ) và tính lợi nhuận tại mỗi ngày.

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit
  • Đây là một cửa sổ trượt suy biến: con trỏ trái (giá thấp nhất) chỉ tiến lên khi tìm thấy một cực tiểu mới. \(O(n)\) thời gian, \(O(1)\) không gian.

Trung bình: Chuỗi con Dài nhất Không có Ký tự Lặp lại

  • Bài toán: tìm độ dài của chuỗi con dài nhất không có bất kỳ ký tự lặp lại nào.

  • Mẫu: mở rộng cửa sổ bằng cách di chuyển right. Khi tìm thấy một ký tự trùng, thu hẹp từ bên trái cho đến khi ký tự trùng bị loại bỏ.

def length_of_longest_substring(s):
    char_index = {}  # character -> chỉ số gần nhất của nó
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # nhảy qua ký tự trùng
        char_index[char] = right
        best = max(best, right - left + 1)

    return best

  • Tại sao char_index[char] >= left: ký tự có thể có trong map từ trước khi cửa sổ hiện tại bắt đầu. Thiếu kiểm tra này, bạn sẽ thu hẹp cửa sổ một cách sai lầm cho một ký tự thực tế không nằm trong cửa sổ hiện tại.

  • Cạm bẫy: dùng một tập hợp (set) và xóa các ký tự từng cái một từ bên trái là đúng nhưng chậm hơn. Cách bản băm nhảy thẳng đến vị trí bên phải.

Khó: Chuỗi con Cửa sổ Nhỏ nhất

  • Bài toán: cho các chuỗi s và t, tìm cửa sổ nhỏ nhất trong s chứa mọi ký tự của t.

  • Mẫu: mở rộng cửa sổ để bao gồm mọi ký tự cần thiết, rồi thu hẹp từ bên trái để tìm cửa sổ hợp lệ nhỏ nhất.

from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""

    need = Counter(t)       # các ký tự ta cần và số lượng của chúng
    have = 0                # có bao nhiêu ký tự độc nhất đã đủ số lượng
    required = len(need)    # có bao nhiêu ký tự độc nhất ta cần

    left = 0
    best = (float('inf'), 0, 0)  # (độ dài, left, right)

    window_counts = {}

    for right in range(len(s)):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1

        # kiểm tra nếu số lượng ký tự này hiện đã đạt yêu cầu
        if char in need and window_counts[char] == need[char]:
            have += 1

        # thu hẹp từ bên trái trong khi cửa sổ hợp lệ
        while have == required:
            # cập nhật best
            if (right - left + 1) < best[0]:
                best = (right - left + 1, left, right)

            # xóa ký tự ngoài cùng bên trái
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in need and window_counts[left_char] < need[left_char]:
                have -= 1
            left += 1

    length, start, end = best
    return s[start:end + 1] if length != float('inf') else ""

  • Cạm bẫy: bộ đếm have là tối ưu hóa then chốt. Thiếu nó, bạn sẽ phải so sánh toàn bộ dict window_counts với need ở mỗi bước, tốn \(O(|\text{các ký tự độc nhất}|)\) mỗi bước. Bộ đếm have làm kiểm tra tính hợp lệ thành \(O(1)\).

  • Cạm bẫy: kiểm tra window_counts[char] == need[char] (không phải >=) đảm bảo ta tăng have đúng một lần cho mỗi ký tự. Nếu dùng >=, ta sẽ đếm thừa.

Mẫu: Tổng tiền tố (Prefix Sums)

  • Một mảng tổng tiền tố (prefix sum) lưu các tổng tích lũy: prefix[i] = sum(arr[0:i]). Một khi xây dựng trong \(O(n)\), bất kỳ tổng mảng con nào cũng tính được trong \(O(1)\): sum(arr[l:r]) = prefix[r] - prefix[l].
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

# tổng của arr[l:r] (bao gồm l, không bao gồm r)
def range_sum(prefix, l, r):
    return prefix[r] - prefix[l]
  • Khi nào dùng: bài toán liên quan đến nhiều truy vấn tổng mảng con, hoặc tìm các mảng con có tổng cụ thể.

Dễ: Truy vấn Tổng một đoạn (Range Sum Query)

  • Bài toán: cho một mảng, trả lời nhiều truy vấn "tổng từ chỉ số \(l\) đến \(r\) là bao nhiêu?"

  • Không có tổng tiền tố: mỗi truy vấn là \(O(n)\). Với tổng tiền tố: \(O(n)\) tiền xử lý, rồi \(O(1)\) mỗi truy vấn.

Trung bình: Tổng mảng con Bằng K

  • Bài toán: đếm số mảng con liên tiếp có tổng bằng \(k\).

  • Cái nhìn sâu về mẫu: một tổng mảng con từ chỉ số \(l\) đến \(r\) bằng prefix[r+1] - prefix[l]. Ta muốn nó bằng \(k\), vậy prefix[l] = prefix[r+1] - k. Với mỗi vị trí, đếm có bao nhiêu tổng tiền tố trước đó bằng current_prefix - k dùng một bản băm.

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    prefix_counts = {0: 1}  # tổng tiền tố rỗng

    for num in nums:
        prefix += num
        # có bao nhiêu tổng tiền tố trước bằng prefix - k?
        count += prefix_counts.get(prefix - k, 0)
        prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1

    return count

  • Cách này kết hợp tổng tiền tố với tra cứu bản băm: \(O(n)\) thời gian, \(O(n)\) không gian.

  • Cạm bẫy: quên khởi tạo prefix_counts = {0: 1}. Tổng tiền tố rỗng (trước mọi phần tử) có tổng 0. Thiếu nó, bạn sẽ bỏ sót các mảng con bắt đầu từ chỉ số 0.

Khó: Tích của Mảng trừ chính nó (Product of Array Except Self)

  • Bài toán: cho một mảng, trả về một mảng trong đó mỗi phần tử là tích của mọi phần tử khác. Bạn không được dùng phép chia.

  • Mẫu: xây dựng tích tiền tố từ trái và tích hậu tố từ phải. Đáp án tại mỗi vị trí là left_product * right_product.

def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    # lượt trái: result[i] = tích của nums[0..i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # lượt phải: nhân với tích của nums[i+1..n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

  • \(O(n)\) thời gian, \(O(1)\) không gian thêm (mảng đầu ra không tính). Cách này dùng chính mảng đầu ra để lưu các tích tiền tố trung gian, rồi nhân thêm tích hậu tố ở lượt thứ hai.

  • Cạm bẫy: nếu mảng chứa một số không, các cách tiếp cận dựa trên chia sẽ thất bại. Cách tiền tố/hậu tố này xử lý số không đúng đắn vì nó không bao giờ chia.

Tóm tắt các Cạm bẫy Thường gặp

Cạm bẫy Ví dụ Sửa
Lệch một đơn vị trong kích thước cửa sổ right - left so với right - left + 1 Vẽ một ví dụ 2 phần tử
Đối số mặc định có thể đổi trong Python def f(seen={}) chia sẻ trạng thái giữa các lời gọi Dùng def f(seen=None)
Nối chuỗi trong vòng lặp s += c là \(O(n^2)\) trong Python Dùng list.append + "".join
Quên {0: 1} trong tổng tiền tố Bỏ sót mảng con bắt đầu tại chỉ số 0 Luôn khởi tạo với tiền tố rỗng
Bản băm trước khi kiểm tra Two Sum: thêm num trước khi kiểm tra phần bù Kiểm tra trước, rồi chèn
Không xử lý trùng lặp Three Sum trả về các bộ ba trùng lặp Bỏ qua các giá trị bằng liên tiếp
Tràn số nguyên Tổng các mảng lớn trong C++/Java Dùng long hoặc kiểm tra giới hạn

Bài tập Tự luyện (NeetCode)

Luyện tập theo thứ tự. Mỗi bài củng cố một mẫu từ tệp này.

Tra cứu Bản băm

Hai con trỏ

Cửa sổ trượt

Tổng tiền tố