Bài Toán Tổng Ba Số Bằng Không

Cho mảng số nguyên, tìm tất cả bộ ba không trùng lặp thỏa mãn tổng bằng 0. Sắp xếp mảng giúp tối ưu quá trình tìm kiếm.

Phương Pháp Giải Quyết

Duyệt từng phần tử làm giá trị đầu tiên, sử dụng hai con trỏ để tìm cặp số phù hợp trong phần còn lại. Để tránh kết quả trùng lặp:

1. Bỏ qua phần tử đầu nếu trùng với giá trị trước đó
2. Khi tìm thấy bộ ba hợp lệ, di chuyển cả hai con trỏ và bỏ qua giá trị trùng

#include<algorithm>
#include<vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& arr) {
        vector<vector<int>> res;
        sort(arr.begin(), arr.end());
        int n = arr.size();
        
        for (int idx = 0; idx < n; idx++) {
            if (idx > 0 && arr[idx] == arr[idx-1]) continue;
            
            int left = idx + 1, right = n - 1;
            while (left < right) {
                int total = arr[idx] + arr[left] + arr[right];
                
                if (total < 0) left++;
                else if (total > 0) right--;
                else {
                    res.push_back({arr[idx], arr[left], arr[right]});
                    while (left < right && arr[left] == arr[left+1]) left++;
                    while (left < right && arr[right] == arr[right-1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
};

Phân Tích Độ Phức Tạp

Thời gian: O(n²) do hai vòng lặp lồng. Không gian: O(1) nếu không tính bộ nhớ cho kết quả.

Bài Toán Đếm Mảng Con Có Tổng Bằng K

Đếm số lượng mảng con liên tiếp có tổng các phần tử bằng giá trị K cho trước.

Phương Pháp Giải Quyết

Sử dụng tổng tiền tố và bảng băm để theo dõi số lần xuất hiện của các tổng trung gian. Với mỗi phần tử:

1. Cập nhật tổng tiền tố hiện tại
2. Kiểm tra sự tồn tại của (tổng_hiện_tại - K) trong bảng băm
3. Tăng biến đếm kết quả dựa trên giá trị băm

#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        unordered_map<int, int> prefixFreq;
        prefixFreq[0] = 1;
        int currentSum = 0, count = 0;
        
        for (int num : nums) {
            currentSum += num;
            if (prefixFreq.find(currentSum - k) != prefixFreq.end()) {
                count += prefixFreq[currentSum - k];
            }
            prefixFreq[currentSum]++;
        }
        return count;
    }
};

Phân Tích Độ Phức Tạp

Thời gian: O(n) do duyệt mảng một lần. Không gian: O(n) để lưu trữ bảng băm.