Khi luyện phỏng vấn thuật toán, có một tình huống mà mình nghĩ khá nhiều Software Engineer từng gặp. Chúng ta đọc đề bài, nhận ra một vài từ khóa quen thuộc và bắt đầu liên tưởng đến những kỹ thuật đã học. Thấy substring thì nghĩ đến Sliding Window, thấy yêu cầu tìm hai số có tổng bằng một giá trị cho trước thì nghĩ đến Hash Map, còn gặp bài toán tính tổng các đoạn liên tiếp thì thử Prefix Sum.
Đây là một phản xạ hữu ích, nhưng cũng có thể trở thành điểm yếu nếu chúng ta chỉ nhớ cách viết code mà chưa hiểu vì sao thuật toán hoạt động. Chẳng hạn, một lời giải Sliding Window chạy đúng với mảng số nguyên dương có thể cho kết quả sai khi xuất hiện số âm. Một Hash Map được cập nhật sai thứ tự có thể khiến thuật toán sử dụng cùng một phần tử hai lần. Thậm chí, chỉ cần thay đổi yêu cầu từ “kiểm tra có tồn tại” sang “đếm tất cả các trường hợp”, cấu trúc dữ liệu chúng ta cần lưu cũng có thể khác hoàn toàn.
Trong công việc Backend, mình cũng gặp kiểu vấn đề tương tự ở một mức độ khác. Khi xử lý dữ liệu giao dịch, trạng thái lệnh hoặc những luồng sự kiện bất đồng bộ, việc lựa chọn công nghệ chỉ là một phần của bài toán. Điều quan trọng hơn là hiểu dữ liệu đang biểu diễn điều gì, những giả định nào phải luôn đúng và hệ thống sẽ phản ứng ra sao khi một giả định bị phá vỡ.
Với thuật toán, tư duy ấy cũng quan trọng không kém. Vì vậy, trong bài viết này, mình muốn đi từ những khái niệm nền tảng đến ba kỹ thuật phổ biến là Hash Map, Sliding Window và Prefix Sum. Mục tiêu không chỉ là giải được một số bài LeetCode bằng Go, mà còn là hiểu được cách hình thành lời giải, cách chứng minh nó đúng và cách phát hiện những trường hợp khiến một thuật toán tưởng chừng hợp lý lại thất bại.
1. Trước khi tối ưu thuật toán, chúng ta cần hiểu điều gì khiến một lời giải đúngLiên kết tới mục này
Giả sử đề bài yêu cầu tìm một đoạn liên tiếp trong mảng có tổng bằng k. Nếu chỉ đọc đến đây, chúng ta chưa có đủ thông tin để lựa chọn thuật toán. Bài toán có thể yêu cầu kiểm tra xem đoạn đó có tồn tại hay không, đếm số đoạn thỏa mãn, tìm đoạn dài nhất hoặc tìm đoạn ngắn nhất. Mỗi yêu cầu cần một cách lưu trữ thông tin khác nhau, dù dữ liệu đầu vào trông gần như giống hệt.
Chúng ta cũng cần phân biệt một số thuật ngữ thường gặp. Subarray là một đoạn gồm các phần tử liên tiếp trong mảng, substring là một đoạn ký tự liên tiếp trong chuỗi, còn subsequence cho phép bỏ qua một số phần tử nhưng phải giữ nguyên thứ tự tương đối. Ví dụ, trong chuỗi "abcde", "bcd" là substring, còn "ace" là subsequence nhưng không phải substring. Sự khác biệt này ảnh hưởng trực tiếp đến việc chúng ta có thể sử dụng Sliding Window hay không.
Một yếu tố khác thường bị xem nhẹ là constraints, tức những giới hạn và điều kiện của đề bài. Mảng có số âm không? Có phần tử trùng nhau không? Độ dài mảng có thể lên đến một triệu không? Đầu vào là ASCII hay Unicode? Tổng các phần tử có thể vượt giới hạn kiểu số nguyên đang sử dụng không? Đây không chỉ là thông tin để tối ưu performance, mà đôi khi là điều kiện quyết định một thuật toán có đúng hay không.
Invariant là gì và vì sao nó quan trọng?Liên kết tới mục này
Trong thuật toán, loop invariant là một tính chất hoặc điều kiện được bảo đảm luôn đúng tại một thời điểm xác định của mỗi lần lặp. Nó giúp chúng ta giải thích tại sao thuật toán đang duy trì trạng thái hợp lệ và tại sao kết quả cuối cùng đáng tin cậy.
Hãy tưởng tượng bạn đang duyệt một mảng từ trái sang phải để tìm giá trị lớn nhất. Sau mỗi lần xử lý một phần tử, biến maxValue phải lưu giá trị lớn nhất trong tất cả các phần tử đã duyệt. Đó là invariant của thuật toán.
func findMax(nums []int) (int, bool) {
if len(nums) == 0 {
return 0, false
}
maxValue := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > maxValue {
maxValue = nums[i]
}
}
return maxValue, true
}Để chứng minh invariant này đúng, chúng ta có thể suy luận theo ba bước.
Khởi tạo (Initialization): Trước vòng lặp, maxValue bằng phần tử đầu tiên. Vì mới xét đúng một phần tử, đây hiển nhiên là giá trị lớn nhất trong phần dữ liệu đã xử lý.
Duy trì (Maintenance): Giả sử trước một lần lặp, maxValue đã là giá trị lớn nhất của các phần tử trước đó. Khi đọc thêm nums[i], chúng ta so sánh nó với maxValue và cập nhật nếu cần. Sau bước này, maxValue tiếp tục là giá trị lớn nhất của toàn bộ phần đã duyệt.
Kết thúc (Termination): Khi vòng lặp kết thúc, tất cả phần tử đều đã được xử lý. Vì invariant vẫn đúng, maxValue chính là giá trị lớn nhất của toàn bộ mảng.
Ba bước này tạo thành một cách chứng minh tính đúng đắn rất phổ biến trong khoa học máy tính. Chúng ta không cần viết chứng minh hình thức cho mọi bài phỏng vấn, nhưng nên hình thành thói quen tự hỏi: Sau mỗi lần lặp, điều gì chắc chắn phải đúng?
Câu hỏi này đặc biệt hữu ích với Hash Map và Sliding Window, vì cả hai đều liên tục cập nhật một trạng thái trung gian. Nếu trạng thái ấy không còn đáp ứng invariant, lời giải có thể sai dù cú pháp và độ phức tạp đều có vẻ hợp lý.
2. Hash Map: Từ tra cứu nhanh đến cách ghi nhớ những gì đã xảy raLiên kết tới mục này
Hash Map là cấu trúc dữ liệu lưu trữ các cặp khóa và giá trị. Trong Go, chúng ta sử dụng kiểu map, chẳng hạn map[string]int để ánh xạ một chuỗi đến một số nguyên. Với những khóa có phép băm và so sánh hiệu quả, các thao tác tra cứu, thêm và cập nhật thường có thời gian O(1) kỳ vọng, dù không được bảo đảm O(1) trong mọi trường hợp.
Điều làm Hash Map hữu ích trong thuật toán không chỉ là tốc độ tra cứu. Nó cho phép chúng ta ghi nhớ một phần thông tin của dữ liệu đã xử lý, để khi gặp phần tử mới, không phải duyệt lại toàn bộ những phần tử trước đó.
Bài toán Two Sum: Tìm hai phần tử có tổng bằng targetLiên kết tới mục này
Cho mảng số nguyên nums và số nguyên target, hãy trả về chỉ số của hai phần tử khác nhau có tổng bằng target. Giả sử đề bài bảo đảm có đúng một đáp án hợp lệ.
Ví dụ:
Input:
nums = [2, 7, 11, 15]
target = 9
Output:
[0, 1]
Giải thích:
nums[0] + nums[1] = 2 + 7 = 9Cách đơn giản nhất là sử dụng hai vòng lặp để kiểm tra mọi cặp phần tử. Nếu mảng có n phần tử, số cặp tối đa cần xét là n × (n - 1) / 2, nên thời gian thực hiện tăng theo O(n²).
Tuy nhiên, chúng ta có thể thay đổi cách đặt câu hỏi. Khi đang xét một phần tử có giá trị x, điều chúng ta thực sự cần biết không phải là mọi phần tử trước đó có giá trị bao nhiêu, mà là liệu có phần tử nào bằng target - x hay không. Giá trị target - x thường được gọi là complement, tức phần còn thiếu để tạo thành tổng mong muốn.
Nếu lưu những giá trị đã gặp vào Hash Map, chúng ta có thể kiểm tra complement mà không cần duyệt lại toàn bộ mảng.
func twoSum(nums []int, target int) []int {
seen := make(map[int]int)
for i, num := range nums {
complement := target - num
if j, exists := seen[complement]; exists {
return []int{j, i}
}
seen[num] = i
}
return nil
}Ở đây, seen lưu ánh xạ từ giá trị phần tử đến vị trí đã gặp. Khi duyệt đến 7, chúng ta tính complement = 9 - 7 = 2. Vì giá trị 2 đã được lưu ở index 0, thuật toán trả về [0, 1].
Điểm quan trọng nằm ở thứ tự tra cứu trước, cập nhật sau. Giả sử đầu vào chỉ có một phần tử [3] và target = 6. Nếu thêm 3 vào map trước rồi tìm complement, chúng ta có thể tìm thấy chính phần tử vừa thêm và trả về cùng một index hai lần. Điều này vi phạm yêu cầu phải chọn hai vị trí khác nhau.
Invariant ở đây là: Trước khi xử lý phần tử tại index i, Hash Map chỉ chứa thông tin về các phần tử có index nhỏ hơn i. Nhờ vậy, nếu tìm thấy complement, chúng ta biết chắc đó là một phần tử khác với phần tử hiện tại.
Với một lần duyệt và các thao tác map O(1) kỳ vọng, thời gian tổng thể giảm từ O(n²) xuống O(n) kỳ vọng. Đổi lại, chúng ta sử dụng thêm O(n) bộ nhớ trong trường hợp xấu nhất.
Group Anagrams: Khi bài toán không phải tìm kiếm mà là phân nhómLiên kết tới mục này
Hash Map còn hữu ích trong những bài toán không liên quan đến tổng hoặc vị trí. Một ví dụ rất hay là Group Anagrams, bài toán số 49 trên LeetCode.
Trước hết, anagram là hai chuỗi có cùng số lượng của từng ký tự, nhưng thứ tự ký tự có thể khác nhau. Chẳng hạn "eat", "tea" và "ate" là anagram vì mỗi chuỗi đều chứa một chữ e, một chữ a và một chữ t. Ngược lại, "eat" và "east" không phải anagram vì chuỗi thứ hai có thêm ký tự s.
Đề bài yêu cầu: Cho một danh sách các chuỗi, hãy gom những chuỗi là anagram của nhau vào cùng một nhóm. Thứ tự các nhóm và thứ tự phần tử trong nhóm không quan trọng.
Input:
["eat", "tea", "tan", "ate", "nat", "bat"]
Output:
[
["eat", "tea", "ate"],
["tan", "nat"],
["bat"]
]Nếu so sánh từng chuỗi với tất cả những chuỗi còn lại, chúng ta phải thực hiện nhiều phép so sánh không cần thiết. Thay vào đó, hãy tìm một cách biểu diễn chung cho mọi chuỗi thuộc cùng nhóm.
Với giả định đầu vào chỉ chứa chữ thường tiếng Anh từ a đến z, chúng ta có thể đếm số lần xuất hiện của 26 ký tự. Ví dụ, "eat" và "tea" đều có số lượng a = 1, e = 1, t = 1, các ký tự còn lại bằng 0. Vì thế, chúng có cùng một khóa.
Trong Go, một mảng cố định [26]int có thể dùng trực tiếp làm khóa của map vì mảng có các phần tử so sánh được là một kiểu dữ liệu comparable.
func groupAnagrams(strs []string) [][]string {
groups := make(map[[26]int][]string)
for _, word := range strs {
var key [26]int
for i := 0; i < len(word); i++ {
key[word[i]-'a']++
}
groups[key] = append(groups[key], word)
}
result := make([][]string, 0, len(groups))
for _, group := range groups {
result = append(result, group)
}
return result
}Ở mỗi chuỗi, chúng ta tạo một mảng đếm mới. Những chuỗi có cùng số lượng của từng ký tự sẽ tạo ra cùng một khóa và được đưa vào cùng nhóm. Nếu có m chuỗi với tổng số ký tự là L, việc tạo khóa tốn O(L) thời gian; các thao tác map có chi phí kỳ vọng, và mỗi khóa có kích thước cố định 26 phần tử. Bộ nhớ bổ sung gồm dữ liệu nhóm và các khóa được lưu.
Điểm đáng học ở Group Anagrams không chỉ là cách dùng map[[26]int][]string, mà là khái niệm canonical representation, tức một cách biểu diễn chuẩn để những đối tượng tương đương có cùng một khóa. Chúng ta cũng có thể dùng chuỗi đã sắp xếp làm khóa, nhưng cách đó có chi phí sắp xếp ký tự cho từng chuỗi.
Cần lưu ý rằng implementation trên chỉ hợp lệ với chữ thường ASCII a–z. Nếu đầu vào chứa chữ hoa, dấu tiếng Việt hoặc Unicode nói chung, chúng ta phải thiết kế lại cách biểu diễn khóa. Đây chính là lý do cần đọc kỹ constraints trước khi lựa chọn giải pháp.
Một sai lầm khác là sử dụng tổng mã ký tự làm khóa. Chẳng hạn "ad" và "bc" có tổng mã ASCII bằng nhau nhưng không phải anagram. Hash Map có thể tra cứu rất nhanh, nhưng nếu khóa không biểu diễn đúng quan hệ tương đương, kết quả vẫn sai.
3. Sliding Window: Tái sử dụng thông tin thay vì kiểm tra lại mọi đoạnLiên kết tới mục này
Sliding Window là kỹ thuật duy trì một đoạn dữ liệu liên tiếp, thường được xác định bằng hai con trỏ left và right. Khi right di chuyển, cửa sổ mở rộng để nhận thêm dữ liệu. Khi left di chuyển, cửa sổ thu hẹp để loại bỏ phần không còn cần thiết.
Điều quan trọng là trạng thái của cửa sổ được cập nhật tăng dần. Chúng ta không phải tính lại toàn bộ thông tin của đoạn sau mỗi lần dịch chuyển.
Bài toán Longest Substring Without Repeating CharactersLiên kết tới mục này
Cho một chuỗi s, hãy tìm độ dài của substring dài nhất không chứa ký tự lặp lại.
Input:
s = "abcabcbb"
Output:
3
Giải thích:
"abc" là substring dài nhất
không có ký tự lặp, độ dài bằng 3.Một cách giải trực tiếp là liệt kê tất cả substring rồi kiểm tra xem từng đoạn có ký tự trùng hay không. Với chuỗi dài n, số substring không rỗng là n(n+1)/2, và nếu mỗi đoạn lại được kiểm tra từ đầu, thời gian thực hiện có thể lên đến O(n³).
Sliding Window cho phép giải bài toán trong O(n) thời gian kỳ vọng bằng cách duy trì một cửa sổ luôn chứa các ký tự khác nhau.
Để hiểu cách hoạt động, hãy xét chuỗi "abba".
| Bước | Ký tự mới | Cửa sổ sau xử lý | `left` | Độ dài |
|---|---|---|---|---|
| 1 | `a` | "a" | 0 | 1 |
| 2 | `b` | "ab" | 0 | 2 |
| 3 | `b` | "b" | 2 | 1 |
| 4 | `a` | "ba" | 2 | 2 |
Khi gặp chữ b thứ hai ở index 2, chúng ta biết lần xuất hiện trước của b nằm ở index 1. Nếu tiếp tục giữ left = 0, cửa sổ "abb" sẽ chứa ký tự lặp. Vì vậy, phải chuyển left đến vị trí ngay sau lần xuất hiện trước, tức index 2.
Đến khi gặp chữ a ở index 3, mặc dù a đã từng xuất hiện ở index 0, vị trí đó đã nằm ngoài cửa sổ hiện tại. Vì vậy, không cần thu hẹp cửa sổ.
Đây là một chi tiết rất dễ sai. Nếu cứ gặp ký tự đã xuất hiện là gán left = previous + 1, con trỏ left có thể di chuyển ngược, khiến cửa sổ trở nên không hợp lệ.
func lengthOfLongestSubstring(s string) int {
lastSeen := make(map[byte]int)
left := 0
best := 0
for right := 0; right < len(s); right++ {
ch := s[right]
if previous, exists := lastSeen[ch]; exists && previous >= left {
left = previous + 1
}
lastSeen[ch] = right
currentLength := right - left + 1
if currentLength > best {
best = currentLength
}
}
return best
}Implementation này xử lý chuỗi theo byte, phù hợp với đầu vào ASCII. Nếu muốn xử lý theo Unicode code point, có thể chuyển chuỗi thành []rune; còn nếu yêu cầu đếm ký tự hiển thị như người dùng nhìn thấy, cần xem xét cả grapheme cluster.
Invariant của thuật toán là: Sau khi xử lý vị trí right, cửa sổ từ left đến right không chứa ký tự lặp, đồng thời left là vị trí bắt đầu nhỏ nhất có thể để cửa sổ kết thúc tại right vẫn hợp lệ.
Tại sao invariant này được duy trì? Trước khi thêm ký tự mới, cửa sổ đã hợp lệ. Khi thêm một ký tự, chỉ có ký tự vừa thêm mới có thể tạo ra sự trùng lặp. Nếu ký tự đó từng xuất hiện tại vị trí p bên trong cửa sổ, chúng ta buộc phải bỏ mọi phần tử từ left đến p. Sau khi đặt left = p + 1, cửa sổ lại hợp lệ. Nếu vị trí cũ nằm ngoài cửa sổ, không cần thay đổi gì.
Vì left luôn là điểm bắt đầu sớm nhất có thể cho một cửa sổ hợp lệ kết thúc tại right, độ dài right - left + 1 là lớn nhất đối với điểm kết thúc ấy. Khi lấy giá trị lớn nhất qua tất cả vị trí right, chúng ta nhận được đáp án toàn cục.
Vì sao hai vòng lặp lồng nhau vẫn có thể chạy O(n)?Liên kết tới mục này
Một phiên bản khác của bài toán sử dụng frequency map và vòng lặp for bên trong để thu hẹp cửa sổ:
func longestUniqueSubstring(s string) int {
frequency := make(map[byte]int)
left, best := 0, 0
for right := 0; right < len(s); right++ {
frequency[s[right]]++
for frequency[s[right]] > 1 {
frequency[s[left]]--
left++
}
if length := right - left + 1; length > best {
best = length
}
}
return best
}Nhìn vào hai vòng lặp, nhiều người có thể nghĩ ngay đến O(n²). Nhưng độ phức tạp phải được tính dựa trên tổng số thao tác, không chỉ dựa vào số tầng vòng lặp.
Con trỏ right đi qua mỗi vị trí đúng một lần. Con trỏ left cũng chỉ tiến về phía trước và không bao giờ quay lại, nên trong toàn bộ chương trình, nó tăng tối đa n lần. Do đó, tổng số lần thực hiện phần thân của vòng lặp thu hẹp không vượt quá n, dù tại một số bước nó có thể chạy nhiều lần.
Đây là ví dụ của amortized analysis, hay phân tích khấu hao: thay vì đánh giá chi phí của một lần lặp riêng lẻ, chúng ta xét tổng chi phí trên toàn bộ chuỗi thao tác. Với thao tác map O(1) kỳ vọng, tổng thời gian vẫn là O(n) kỳ vọng.
Tuy nhiên, không phải cứ có hai con trỏ là chắc chắn đạt O(n). Nếu mỗi lần dịch chuyển lại quét toàn bộ cửa sổ, chi phí có thể tăng lên. Chính việc tái sử dụng trạng thái và giới hạn tổng số lần di chuyển mới tạo ra hiệu quả.
4. Khi nào Sliding Window hoạt động và tại sao số âm có thể khiến nó thất bại?Liên kết tới mục này
Xét bài toán Minimum Size Subarray Sum: Cho một mảng số nguyên dương nums và số nguyên dương target, hãy tìm độ dài nhỏ nhất của một subarray có tổng lớn hơn hoặc bằng target. Nếu không có đoạn nào thỏa mãn, trả về 0.
Input:
nums = [2, 3, 1, 2, 4, 3]
target = 7
Output:
2
Giải thích:
Subarray [4, 3] có tổng bằng 7
và chỉ gồm 2 phần tử.Vì tất cả phần tử đều dương, khi mở rộng cửa sổ sang phải, tổng chỉ có thể tăng. Khi loại phần tử bên trái, tổng chỉ có thể giảm. Đây là tính chất đơn điệu giúp chúng ta quyết định khi nào nên mở rộng và khi nào nên thu hẹp.
Chúng ta bắt đầu với cửa sổ rỗng và tổng bằng 0. Mỗi lần tăng right, cộng thêm phần tử mới. Khi tổng đạt ít nhất target, cửa sổ hiện tại là một ứng viên hợp lệ. Chúng ta ghi nhận độ dài rồi thử loại phần tử ở đầu trái để tìm một đoạn ngắn hơn. Nếu tổng không còn đạt target, chúng ta quay lại mở rộng cửa sổ.
func minSubArrayLen(target int, nums []int) int {
left := 0
sum := int64(0)
best := len(nums) + 1
for right, value := range nums {
sum += int64(value)
for sum >= int64(target) {
length := right - left + 1
if length < best {
best = length
}
sum -= int64(nums[left])
left++
}
}
if best == len(nums)+1 {
return 0
}
return best
}Tại sao việc loại phần tử bên trái không khiến chúng ta bỏ lỡ đáp án tối ưu? Khi cửa sổ [left, right] đã đạt target, chúng ta đã ghi nhận độ dài của nó. Mọi đoạn bắt đầu ở cùng left nhưng kết thúc xa hơn right đều dài hơn, nên không thể là ứng viên tốt hơn. Vì thế, có thể thử tăng left để tìm đoạn ngắn hơn.
Ngược lại, khi tổng nhỏ hơn target, việc tiếp tục loại số dương chỉ khiến tổng giảm. Muốn đạt target trở lại, chúng ta cần mở rộng cửa sổ sang phải. Chính tính chất này bảo đảm các ứng viên bị bỏ qua không thể tạo ra một đáp án tốt hơn.
Nhưng nếu mảng chứa số âm, lập luận trên không còn đúng.
Hãy xét:
nums = [1, -1, 5]
target = 5Đáp án đúng là 1, vì subarray [5] đã có tổng bằng target. Tuy nhiên, thuật toán Sliding Window vừa viết sẽ mở rộng đến hết mảng, khi đó tổng bằng 1 + (-1) + 5 = 5 và độ dài bằng 3. Sau khi loại phần tử đầu tiên là 1, tổng giảm xuống 4, khiến vòng lặp thu hẹp dừng lại. Thuật toán không tiếp tục loại -1, dù thao tác ấy sẽ khiến tổng tăng từ 4 lên 5 và tạo ra đoạn [5] dài 1.
Sai lầm không nằm ở cú pháp code, mà ở giả định rằng loại phần tử bên trái luôn làm tổng giảm. Giả định này đúng với số dương nhưng không đúng khi có số âm.
Điều đó không có nghĩa mọi bài toán chứa số âm đều không thể dùng Sliding Window. Chẳng hạn, cửa sổ có kích thước cố định vẫn có thể tính tổng của những số âm bình thường. Vấn đề nằm ở những thuật toán cần tính đơn điệu của tổng để quyết định thu hẹp cửa sổ.
Với bài toán tìm subarray ngắn nhất có tổng ít nhất bằng k khi cho phép số âm, một giải pháp tổng quát hơn là Prefix Sum kết hợp Monotonic Deque. Trước khi tìm hiểu kỹ thuật nâng cao này, chúng ta cần hiểu Prefix Sum hoạt động như thế nào.
5. Prefix Sum: Tại sao tổng của một đoạn có thể được tính bằng một phép trừ?Liên kết tới mục này
Giả sử có mảng:
nums = [2, 4, 1, 3]Nếu muốn tính tổng của các phần tử từ index 1 đến index 2, chúng ta có thể cộng trực tiếp 4 + 1 = 5. Với một truy vấn, cách này không có vấn đề gì. Nhưng nếu phải trả lời hàng trăm nghìn truy vấn tổng trên cùng một mảng, việc cộng lại từng đoạn sẽ lãng phí nhiều công việc.
Prefix Sum giải quyết vấn đề bằng cách tính trước tổng tích lũy. Chúng ta định nghĩa prefix[i] là tổng của i phần tử đầu tiên, nghĩa là các phần tử có index từ 0 đến i - 1.
Với mảng trên, ta có:
| Chỉ số prefix | Các phần tử đã cộng | Giá trị |
|---|---|---|
| `prefix[0]` | Chưa có phần tử nào | 0 |
| `prefix[1]` | 2 | 2 |
| `prefix[2]` | 2 + 4 | 6 |
| `prefix[3]` | 2 + 4 + 1 | 7 |
| `prefix[4]` | 2 + 4 + 1 + 3 | 10 |
Giả sử muốn tính tổng đoạn từ index 1 đến index 2, chúng ta lấy tổng ba phần tử đầu tiên là prefix[3] = 7, rồi trừ tổng một phần tử đầu tiên là prefix[1] = 2. Phần còn lại chính là 4 + 1 = 5.
Tổng quát, với đoạn nửa mở [left, right) — bao gồm left nhưng không bao gồm right — công thức là:
Lý do công thức đúng rất đơn giản: prefix[right] chứa tổng từ đầu mảng đến ngay trước right, còn prefix[left] chứa phần tổng từ đầu mảng đến ngay trước left. Khi lấy hai giá trị trừ nhau, toàn bộ phần đứng trước left bị triệt tiêu, chỉ còn lại tổng của đoạn cần tìm.
func buildPrefixSum(nums []int) []int64 {
prefix := make([]int64, len(nums)+1)
for i, num := range nums {
prefix[i+1] = prefix[i] + int64(num)
}
return prefix
}
func rangeSum(prefix []int64, left, right int) int64 {
return prefix[right] - prefix[left]
}Việc xây dựng Prefix Sum tốn O(n) thời gian và O(n) bộ nhớ. Sau đó, mỗi truy vấn tổng đoạn chỉ cần một phép trừ, tức O(1) thời gian. Cách tiếp cận này đặc biệt phù hợp khi mảng không thay đổi hoặc khi số lượng truy vấn đủ lớn để bù lại chi phí tính trước.
Tuy nhiên, Prefix Sum không chỉ dùng để trả lời truy vấn tổng. Khi kết hợp với Hash Map, nó còn giúp giải những bài toán đếm subarray có tổng bằng một giá trị cho trước, kể cả khi dữ liệu chứa số âm.
6. Prefix Sum kết hợp Hash Map: Hiểu từng bước bài toán Subarray Sum Equals KLiên kết tới mục này
Đây là bài toán số 560 trên LeetCode. Đề bài cho một mảng số nguyên nums, có thể chứa số dương, số âm và số 0, cùng một số nguyên k. Nhiệm vụ là đếm có bao nhiêu subarray không rỗng có tổng đúng bằng k.
Ví dụ:
Input:
nums = [1, -1, 1]
k = 1
Output:
3Có ba subarray thỏa mãn: phần tử [1] ở index 0, đoạn [1, -1, 1] từ index 0 đến index 2 và phần tử [1] ở index 2. Mặc dù hai đoạn đầu và cuối có cùng giá trị [1], chúng nằm ở hai vị trí khác nhau nên được tính là hai subarray khác nhau.
Từ tổng của một đoạn đến việc tìm prefix đã xuất hiệnLiên kết tới mục này
Giả sử chúng ta đang xử lý đến vị trí right trong mảng Prefix Sum. Một subarray bắt đầu tại left và kết thúc ngay trước right có tổng bằng:
Muốn tổng đoạn bằng k, ta cần:
Chuyển vế, ta được:
Điều này có ý nghĩa rất quan trọng. Khi đã biết tổng tích lũy hiện tại, chúng ta không cần thử lại tất cả vị trí bắt đầu. Chỉ cần biết trong các prefix trước đó có bao nhiêu prefix mang giá trị prefix hiện tại - k.
Ví dụ, nếu tổng tích lũy hiện tại bằng 8 và k = 3, chúng ta cần tìm những prefix trước đó có giá trị 5. Mỗi prefix bằng 5 tương ứng với một vị trí bắt đầu khác nhau, và đoạn từ vị trí đó đến vị trí hiện tại sẽ có tổng bằng 3.
Vì một giá trị prefix có thể xuất hiện nhiều lần, chúng ta phải lưu tần suất xuất hiện, không chỉ lưu việc nó có tồn tại hay không. Đó là lý do thuật toán sử dụng map[int64]int64 để ánh xạ giá trị prefix đến số lần nó đã xuất hiện.
Theo dõi thuật toán bằng một ví dụ cụ thểLiên kết tới mục này
Xét:
nums = [1, -1, 1]
k = 1Ban đầu, tổng tích lũy bằng 0. Chúng ta khởi tạo frequency[0] = 1, biểu diễn một prefix rỗng trước phần tử đầu tiên.
| Phần tử vừa đọc | Prefix hiện tại | Giá trị cần tìm (`prefix - k`) | Số prefix phù hợp đã có | Tổng số đoạn |
|---|---|---|---|---|
| Chưa đọc | 0 | — | — | 0 |
| `1` tại index 0 | 1 | 0 | 1 | 1 |
| `-1` tại index 1 | 0 | -1 | 0 | 1 |
| `1` tại index 2 | 1 | 0 | 2 | 3 |
Ở bước đầu, prefix bằng 1 và giá trị cần tìm bằng 0. Trong map đã có một prefix bằng 0, nên chúng ta tìm được đoạn [1] đầu tiên. Sau đó, prefix bằng 1 được lưu lại.
Ở bước thứ hai, prefix trở về 0. Giá trị cần tìm là -1, nhưng chưa có prefix nào bằng -1 nên không tìm được đoạn mới. Chúng ta cập nhật số lần xuất hiện của prefix 0 từ 1 lên 2.
Đến bước thứ ba, prefix lại bằng 1 và giá trị cần tìm bằng 0. Lúc này có hai prefix trước đó bằng 0: prefix rỗng trước khi bắt đầu mảng và prefix sau khi xử lý hai phần tử [1, -1]. Chúng tương ứng với hai subarray hợp lệ là [1, -1, 1] và [1] ở index 2. Vì vậy, số lượng đáp án tăng thêm 2, từ 1 lên 3.
func subarraySum(nums []int, k int) int64 {
frequency := map[int64]int64{
0: 1,
}
var prefix int64
var count int64
for _, num := range nums {
prefix += int64(num)
need := prefix - int64(k)
count += frequency[need]
frequency[prefix]++
}
return count
}Thuật toán duyệt mảng đúng một lần, thực hiện các thao tác Hash Map có thời gian O(1) kỳ vọng, nên tổng thời gian là O(n) kỳ vọng. Trong trường hợp xấu nhất, chúng ta có thể lưu O(n) giá trị prefix khác nhau.
Vì sao `frequency[0] = 1` không phải một mẹo viết code?Liên kết tới mục này
Để hiểu điều này, hãy xét mảng chỉ có một phần tử:
nums = [3]
k = 3Sau khi đọc phần tử 3, prefix hiện tại bằng 3. Muốn tìm một đoạn có tổng bằng 3, chúng ta cần một prefix trước đó có giá trị 3 - 3 = 0.
Prefix bằng 0 ở đây chính là trạng thái trước khi đọc bất kỳ phần tử nào. Nếu không khởi tạo nó, thuật toán sẽ không nhận ra đoạn [3] bắt đầu từ index 0 là một đáp án hợp lệ.
Nói cách khác, frequency[0] = 1 biểu diễn một prefix có độ dài bằng 0, chứ không phải một subarray rỗng được tính vào kết quả. Prefix rỗng là một mốc hợp lệ để tính hiệu; còn subarray được đếm phải kéo dài từ mốc đó đến một vị trí phía sau, nên vẫn có ít nhất một phần tử.
Vì sao phải tra cứu trước khi cập nhật map?Liên kết tới mục này
Đây là một trong những chi tiết quan trọng nhất của bài toán. Hãy xét đầu vào:
nums = [5]
k = 0Đáp án đúng là 0, vì subarray không rỗng duy nhất là [5], có tổng bằng 5 chứ không phải 0.
Giả sử chúng ta viết sai thứ tự như sau:
prefix += int64(num)
frequency[prefix]++ // Sai thứ tự
need := prefix - int64(k)
count += frequency[need]Ban đầu, map chứa {0: 1}. Sau khi đọc phần tử 5, prefix bằng 5. Nếu cập nhật map ngay lập tức, map sẽ chứa thêm {5: 1}. Vì k = 0, giá trị cần tìm là 5 - 0 = 5, và phép tra cứu sẽ thấy chính prefix vừa được thêm vào. Thuật toán kết luận có một subarray tổng bằng 0, dù thực tế không có đoạn nào như vậy.
Vậy nó đã đếm nhầm đoạn nào? Nó đang lấy hiệu của prefix hiện tại với chính prefix hiện tại:
Hai mốc bắt đầu và kết thúc trùng nhau, nên đoạn tương ứng có độ dài bằng 0 và không chứa phần tử nào. Đây là subarray rỗng, không hợp lệ theo đề bài.
Để tránh lỗi này, chúng ta phải bảo đảm rằng khi tra cứu prefix - k, map chỉ chứa những prefix ở các mốc trước prefix hiện tại. Sau khi hoàn thành việc đếm, chúng ta mới thêm prefix hiện tại để phục vụ các bước tiếp theo.
Đó chính là invariant của thuật toán: Trước khi đếm các subarray kết thúc tại vị trí hiện tại, frequency map chỉ lưu số lần xuất hiện của những prefix nằm trước mốc kết thúc hiện tại.
Thứ tự này không phải vấn đề phong cách lập trình. Nó là một phần của chứng minh tính đúng đắn.
Vì sao số lượng subarray có thể vượt giới hạn int32?Liên kết tới mục này
Một chi tiết khác dễ bị bỏ qua là kiểu dữ liệu dùng để lưu đáp án. Hãy xét mảng gồm 100.000 phần tử, tất cả đều bằng 0, với k = 0.
Vì tất cả phần tử đều bằng 0, bất kỳ subarray không rỗng nào cũng có tổng bằng 0. Như vậy, bài toán trở thành: Một mảng có 100.000 phần tử chứa tất cả bao nhiêu đoạn liên tiếp không rỗng?
Hãy bắt đầu với mảng nhỏ hơn để dễ hình dung:
nums = [0, 0, 0]Có ba subarray độ dài 1, gồm các phần tử tại index 0, 1 và 2. Có hai subarray độ dài 2, gồm đoạn index 0–1 và đoạn index 1–2. Cuối cùng, có một subarray độ dài 3, là toàn bộ mảng. Tổng cộng có 3 + 2 + 1 = 6 subarray.
Với mảng có n phần tử, nếu cố định vị trí bắt đầu là index 0, chúng ta có n cách chọn vị trí kết thúc. Nếu bắt đầu ở index 1, chỉ còn n - 1 cách. Tiếp tục như vậy đến phần tử cuối cùng, ta có tổng:
Đây là tổng của các số nguyên từ 1 đến n. Công thức tính là:
Với n = 100000, chúng ta thay trực tiếp vào công thức:
Nghĩa là một mảng gồm 100.000 số 0 có đến 5 tỷ 50 nghìn subarray không rỗng, và tất cả đều có tổng bằng 0.
Trong khi đó, giá trị lớn nhất của số nguyên có dấu 32 bit là:
Số lượng đáp án trong ví dụ lớn hơn giới hạn này, nên nếu sử dụng int32 để lưu biến đếm, chúng ta sẽ gặp lỗi tràn số. Đó là lý do implementation sử dụng int64 cho cả tổng tích lũy và số lượng đáp án.
Cần phân biệt thêm rằng trong Go, kiểu int có kích thước phụ thuộc kiến trúc, thường là 64 bit trên hệ thống 64 bit. Việc sử dụng int64 ở đây giúp biểu đạt rõ yêu cầu về phạm vi giá trị và tránh phụ thuộc không cần thiết vào kiến trúc chạy chương trình. Dĩ nhiên, nếu constraints còn lớn hơn nữa, chúng ta vẫn phải kiểm tra liệu int64 có đủ hay không.
Đây cũng là một bài học có giá trị trong Backend. Những lỗi liên quan đến overflow hoặc dữ liệu biên thường không xuất hiện khi test với vài chục bản ghi, nhưng có thể trở thành vấn đề nghiêm trọng khi hệ thống xử lý dữ liệu lớn hoặc chạy tích lũy trong thời gian dài.
7. Làm sao nhận biết nên sử dụng Hash Map, Sliding Window hay Prefix Sum?Liên kết tới mục này
Sau khi hiểu ba kỹ thuật, điều quan trọng là tránh biến chúng thành những công thức máy móc. Một bài toán có thể chứa substring nhưng không phù hợp với Sliding Window. Một bài toán liên quan đến tổng có thể cần Prefix Sum thay vì Two Pointers. Một bài toán dùng Hash Map cũng có thể cần lưu vị trí đầu tiên, vị trí cuối cùng, tần suất hoặc một khóa đại diện cho cả nhóm dữ liệu.
| Dấu hiệu của bài toán | Hướng tiếp cận | Điều cần kiểm tra |
|---|---|---|
| Tìm phần tử đã xuất hiện | Hash Set / Hash Map | Cần biết tồn tại, vị trí hay tần suất? |
| Tìm hai phần tử có tổng bằng target | Hash Map | Có được dùng cùng một index hai lần không? |
| Gom các chuỗi tương đương | Hash Map với khóa chuẩn hóa | Khóa có phân biệt đúng các nhóm không? |
| Substring dài nhất không lặp | Sliding Window | Cửa sổ có luôn hợp lệ không? |
| Subarray ngắn nhất đạt tổng, toàn số dương | Sliding Window | Tổng có tính đơn điệu khi dịch biên không? |
| Nhiều truy vấn tổng trên mảng cố định | Prefix Sum | Mảng có thay đổi giữa các truy vấn không? |
| Đếm subarray tổng bằng K, có số âm | Prefix Sum + Frequency Map | Có lưu đúng tần suất và thứ tự prefix không? |
| Subarray ngắn nhất đạt tổng K, có số âm | Prefix Sum + Monotonic Deque | Cần duy trì các prefix ứng viên như thế nào? |
Bảng trên nên được xem là gợi ý nhận diện, không phải quy tắc tuyệt đối. Khi gặp bài toán mới, chúng ta vẫn cần phân tích yêu cầu đầu ra, constraints và những tính chất có thể khai thác.
Một cách mình thấy hữu ích là bắt đầu từ brute force, dù nó chưa tối ưu. Brute force cho chúng ta biết chính xác những ứng viên nào đang được xét và điều kiện nào khiến một ứng viên hợp lệ. Sau đó, hãy tìm phần công việc đang bị lặp lại: có phải đang tính lại tổng của cùng một đoạn, kiểm tra lại những ký tự đã gặp hoặc duyệt lại toàn bộ dữ liệu quá khứ chỉ để tìm một giá trị?
Hash Map giúp ghi nhớ thông tin quá khứ, Sliding Window giúp duy trì trạng thái của một đoạn liên tiếp, còn Prefix Sum giúp biến phép tính tổng đoạn thành phép trừ giữa hai mốc. Khi hiểu được công việc lặp lại nằm ở đâu, việc lựa chọn kỹ thuật sẽ tự nhiên hơn nhiều.
8. Từ bài toán LeetCode đến tư duy thiết kế hệ thống BackendLiên kết tới mục này
Có một quan điểm khá phổ biến rằng luyện thuật toán chủ yếu phục vụ phỏng vấn, bởi trong công việc thực tế chúng ta hiếm khi phải tự viết những bài như Two Sum hay Longest Substring. Mình nghĩ nhận định ấy đúng nếu chỉ xét các bài toán cụ thể, nhưng chưa phản ánh hết giá trị của việc học thuật toán.
Trong công việc Backend, đặc biệt với các hệ thống xử lý dữ liệu giao dịch và sự kiện bất đồng bộ, mình thường quan tâm đến những câu hỏi như: Thông tin nào cần được lưu để xử lý sự kiện tiếp theo? Có cần đọc lại toàn bộ lịch sử mỗi lần cập nhật không? Điều gì phải luôn đúng trước và sau khi một trạng thái thay đổi? Nếu sự kiện đến trùng hoặc sai thứ tự thì hệ thống sẽ xử lý như thế nào?
Những câu hỏi ấy có nhiều điểm tương đồng với tư duy đằng sau Hash Map, Sliding Window và Prefix Sum.
Ví dụ, khi xử lý một luồng sự kiện, chúng ta có thể duy trì những thống kê tích lũy thay vì tính lại từ đầu. Khi cần phát hiện identifier trùng lặp, chúng ta phải xác định trạng thái nào cần được ghi nhớ và phạm vi hiệu lực của nó. Khi xử lý dữ liệu theo từng khoảng thời gian, chúng ta phải cân nhắc cách duy trì cửa sổ dữ liệu và loại bỏ những sự kiện đã hết hiệu lực.
Dĩ nhiên, không thể áp dụng trực tiếp một lời giải LeetCode để giải quyết mọi vấn đề production. Một Hash Map trong bộ nhớ không tự động bảo đảm idempotency trong hệ thống phân tán; một Sliding Window đơn giản cũng chưa giải quyết được những vấn đề như event-time processing, late arrivals, concurrency hoặc recovery sau khi service restart. Nhưng các kỹ thuật thuật toán giúp rèn luyện một năng lực nền tảng: xác định trạng thái cần duy trì, hiểu các điều kiện bất biến và phân tích vì sao một giải pháp có thể đúng hoặc sai.
Đó là điều mình cho rằng đáng học hơn cả việc ghi nhớ hàng chục template.
9. Một cách luyện thuật toán giúp hiểu sâu và nhớ lâu hơnLiên kết tới mục này
Nếu chỉ đọc lời giải mẫu, chúng ta rất dễ có cảm giác mình đã hiểu bài. Code trông hợp lý, độ phức tạp đã được giải thích và kết quả test đều đúng. Nhưng vài ngày sau, khi gặp một biến thể hơi khác, chúng ta lại không biết bắt đầu từ đâu.
Để tránh tình trạng này, mình thích luyện mỗi bài theo một trình tự rõ ràng. Trước tiên, đọc kỹ đề và tự viết lại yêu cầu bằng lời của mình. Tiếp theo, xây dựng một lời giải brute force để hiểu toàn bộ không gian ứng viên. Sau đó, tìm cách loại bỏ những phép tính lặp lại và xác định invariant mà lời giải tối ưu cần duy trì. Cuối cùng, viết code, tự chứng minh tính đúng đắn và chủ động tìm các trường hợp phản ví dụ.
Chẳng hạn, với bài Longest Substring Without Repeating Characters, những chuỗi như "abba" hoặc "pwwkew" giúp kiểm tra liệu con trỏ left có bị di chuyển ngược hay không. Với Subarray Sum Equals K, các trường hợp [0, 0, 0] với k = 0 giúp kiểm tra cách đếm những prefix trùng nhau, còn [5] với k = 0 giúp phát hiện lỗi cập nhật map trước khi tra cứu.
func TestSubarraySum(t *testing.T) {
cases := []struct {
nums []int
k int
want int64
}{
{[]int{1, 1, 1}, 2, 2},
{[]int{1, -1, 1}, 1, 3},
{[]int{0, 0, 0}, 0, 6},
{[]int{5}, 0, 0},
{[]int{}, 0, 0},
}
for _, tc := range cases {
got := subarraySum(tc.nums, tc.k)
if got != tc.want {
t.Errorf(
"nums=%v, k=%d, got=%d, want=%d",
tc.nums, tc.k, got, tc.want,
)
}
}
}Đoạn test trên cần đặt trong file Go test, ví dụ algorithms_test.go, với import "testing" và hàm subarraySum` nằm trong cùng package hoặc được import phù hợp.
Một cách kiểm chứng mạnh hơn là viết cả lời giải brute force và lời giải tối ưu, sau đó tạo nhiều mảng nhỏ ngẫu nhiên để so sánh kết quả giữa hai cách. Nếu có sự khác biệt, chúng ta đã tìm được một phản ví dụ cần phân tích. Đây là một dạng differential testing rất hữu ích, đặc biệt khi lời giải tối ưu có nhiều trạng thái và điều kiện biên.
Mình nghĩ khả năng tự tìm ra phản ví dụ quan trọng không kém khả năng viết lời giải đúng. Nó cho thấy chúng ta không chỉ hiểu thuật toán hoạt động như thế nào trong trường hợp thuận lợi, mà còn hiểu điều kiện nào có thể khiến nó thất bại.
Kết luận: Điều đáng nhớ nhất không phải là templateLiên kết tới mục này
Hash Map, Sliding Window và Prefix Sum đều là những kỹ thuật nền tảng, nhưng giá trị của chúng nằm ở những ý tưởng sâu hơn cú pháp lập trình. Hash Map giúp chúng ta lưu lại thông tin cần thiết của dữ liệu đã xử lý. Sliding Window giúp tái sử dụng trạng thái của một đoạn liên tiếp, với điều kiện chúng ta có thể chứng minh việc dịch chuyển các biên không bỏ lỡ đáp án. Prefix Sum biến tổng của một đoạn thành hiệu của hai mốc, và khi kết hợp với Hash Map, nó giúp giải quyết những bài toán đếm có cả số âm và những prefix trùng nhau.
Nếu chỉ nhớ code, chúng ta có thể giải nhanh những bài quen thuộc. Nhưng nếu hiểu invariant, biết cách suy luận từ brute force, phân tích constraints và tự xây dựng phản ví dụ, chúng ta sẽ có khả năng giải những bài toán chưa từng gặp.
Trong phỏng vấn, viết được một lời giải O(n) là một kết quả tốt. Nhưng giải thích được vì sao nó đúng, những giả định nào đang được sử dụng và điều gì xảy ra khi giả định thay đổi mới thực sự thể hiện chiều sâu tư duy kỹ thuật.
Với mình, đó cũng là một trong những điểm kết nối rõ nhất giữa việc luyện thuật toán và công việc Software Engineer: đừng chỉ tìm cách khiến chương trình chạy đúng với dữ liệu đang có; hãy hiểu vì sao nó đúng và trong những điều kiện nào nó sẽ tiếp tục đúng.