454. Tổng Bốn Số II

Bài toán yêu cầu tìm số lượng bộ bốn phần tử (a, b, c, d) sao cho a từ nums1, b từ nums2, c từ nums3, và d từ nums4, có tổng a + b + c + d = 0.

Một cách tiếp cận hiệu quả là chia bài toán thành hai phần. Đầu tiên, chúng ta tính tất cả các tổng có thể của các cặp phần tử từ nums1 và nums2, lưu trữ tần suất của chúng vào một bảng băm (hash map). Sau đó, chúng ta duyệt qua tất cả các cặp phần tử từ nums3 và nums4. Với mỗi cặp (c, d), chúng ta tìm xem liệu trong bảng băm có tồn tại một tổng (a + b) nào đó bằng -(c + d) hay không. Nếu có, chúng ta cộng tần suất của tổng đó vào kết quả cuối cùng.

Mã C++ minh họa:

class Solution {
public:
    int demTongBonSoBangKhong(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3,
                             vector<int>& arr4) {
        // Lưu trữ tần suất của các tổng từ arr1 và arr2
        unordered_map<int, int> tongCapDoiAB; 
        for (int giaTriA : arr1) {
            for (int giaTriB : arr2) {
                tongCapDoiAB[giaTriA + giaTriB]++;
            }
        }

        int soLuongBoBon = 0;
        // Duyệt qua arr3 và arr4, tìm tổng bù
        for (int giaTriC : arr3) {
            for (int giaTriD : arr4) {
                int giaTriCanTim = -(giaTriC + giaTriD);
                // Nếu tổng bù tồn tại trong map, cộng tần suất của nó vào kết quả
                if (tongCapDoiAB.count(giaTriCanTim)) { 
                    soLuongBoBon += tongCapDoiAB[giaTriCanTim];
                }
            }
        }
        return soLuongBoBon;
    }
};

383. Thư Tống Tiền

Bài toán yêu cầu xác định xem một chuỗi chuoiThongDiep (ransom note) có thể được tạo thành từ các ký tự trong chuỗi chuoiTapChi (magazine) hay không. Mỗi ký tự trong chuoiTapChi chỉ có thể được sử dụng một lần.

Phương pháp hiệu quả nhất là sử dụng một mảng tần suất (hoặc hash map) để đếm số lần xuất hiện của từng ký tự. Vì chỉ có các ký tự chữ cái thường trong tiếng Anh, một mảng kích thước 26 là đủ.

1. Đầu tiên, kiểm tra độ dài: nếu chuoiThongDiep dài hơn chuoiTapChi, thì không thể tạo được, trả về false.
2. Khởi tạo một mảng demKyTu có 26 phần tử, tất cả đều bằng 0.
3. Duyệt qua chuoiTapChi: với mỗi ký tự, tăng giá trị tương ứng trong mảng demKyTu lên 1.
4. Duyệt qua chuoiThongDiep: với mỗi ký tự, giảm giá trị tương ứng trong mảng demKyTu xuống 1.
5. Trong quá trình giảm, nếu bất kỳ giá trị nào trong demKyTu trở thành số âm, điều đó có nghĩa là không có đủ ký tự đó trong chuoiTapChi để tạo chuoiThongDiep, vì vậy chúng ta có thể trả về false ngay lập tức.
6. Nếu vòng lặp hoàn thành mà không có giá trị nào âm, điều đó có nghĩa là chuoiThongDiep có thể được tạo, trả về true.

Mã C++ minh họa:

class Solution {
public:
    bool coTheTaoThu(string chuoiThongDiep, string chuoiTapChi) {
        if (chuoiThongDiep.length() > chuoiTapChi.length()) {
            return false; // Chuỗi thông điệp dài hơn tạp chí, không thể tạo
        }

        vector<int> demKyTu(26, 0); // Mảng đếm tần suất ký tự ('a' - 'z')

        // Đếm tần suất các ký tự trong chuoiTapChi
        for (char kyTu : chuoiTapChi) {
            demKyTu[kyTu - 'a']++;
        }

        // Kiểm tra và trừ đi tần suất các ký tự trong chuoiThongDiep
        for (char kyTu : chuoiThongDiep) {
            demKyTu[kyTu - 'a']--;
            if (demKyTu[kyTu - 'a'] < 0) {
                return false; // Không đủ ký tự trong chuoiTapChi
            }
        }
        return true; // Có thể tạo chuoiThongDiep
    }
};

15. Tổng Ba Số

Bài toán tìm tất cả các bộ ba số nguyên (a, b, c) duy nhất trong một mảng danhSachSo sao cho tổng của chúng bằng 0.

Cách tiếp cận hiệu quả cho bài toán này là sử dụng phương pháp hai con trỏ sau khi mảng đã được sắp xếp. Việc sắp xếp mảng cho phép chúng ta bỏ qua các bộ ba trùng lặp và điều chỉnh con trỏ một cách có hệ thống.

1. Sắp xếp mảng danhSachSo.
2. Duyệt qua mảng với một con trỏ ngoài i (cho số a).
   • Để tránh các bộ ba trùng lặp, nếu danhSachSo[i] giống với danhSachSo[i-1], hãy bỏ qua lần lặp này.
   • Nếu danhSachSo[i] (số nhỏ nhất trong bộ ba) đã lớn hơn 0, thì tổng của ba số sẽ luôn dương, vì vậy có thể dừng tìm kiếm và trả về kết quả.
3. Khởi tạo hai con trỏ: conTroTrai = i + 1 (cho số b) và conTroPhai = n - 1 (cho số c), trong đó n là kích thước của mảng.
4. Trong khi conTroTrai < conTroPhai:
   • Tính tổng currentSum = danhSachSo[i] + danhSachSo[conTroTrai] + danhSachSo[conTroPhai].
   • Nếu currentSum < 0, tăng conTroTrai để có số lớn hơn.
   • Nếu currentSum > 0, giảm conTroPhai để có số nhỏ hơn.
   • Nếu currentSum == 0, tìm thấy một bộ ba hợp lệ. Lưu bộ ba này vào kết quả. Sau đó, để tránh trùng lặp, tăng conTroTrai và giảm conTroPhai, bỏ qua các phần tử trùng lặp:
     • Tăng conTroTrai trong khi danhSachSo[conTroTrai] == danhSachSo[conTroTrai + 1].
     • Giảm conTroPhai trong khi danhSachSo[conTroPhai] == danhSachSo[conTroPhai - 1].
     • Cuối cùng, tăng conTroTrai và giảm conTroPhai một lần nữa để di chuyển đến các phần tử khác.

Mã C++ minh họa:

class Solution {
public:
    vector<vector<int>> timBaSoTongBangKhong(vector<int>& danhSachSo) {
        vector<vector<int>> cacBoKetQua;
        sort(danhSachSo.begin(), danhSachSo.end()); // Sắp xếp mảng

        int n = danhSachSo.size();
        for (int i = 0; i < n; ++i) {
            // Nếu số đầu tiên (danhSachSo[i]) đã dương, thì tổng của ba số sẽ luôn dương.
            if (danhSachSo[i] > 0) {
                break;
            }
            // Bỏ qua các phần tử trùng lặp cho số thứ nhất để tránh các bộ ba trùng lặp
            if (i > 0 && danhSachSo[i] == danhSachSo[i - 1]) {
                continue;
            }

            int conTroTrai = i + 1;
            int conTroPhai = n - 1;

            while (conTroTrai < conTroPhai) {
                long long tongHienTai = (long long)danhSachSo[i] + danhSachSo[conTroTrai] + danhSachSo[conTroPhai];

                if (tongHienTai < 0) {
                    conTroTrai++;
                } else if (tongHienTai > 0) {
                    conTroPhai--;
                } else { // tongHienTai == 0
                    cacBoKetQua.push_back({danhSachSo[i], danhSachSo[conTroTrai], danhSachSo[conTroPhai]});

                    // Bỏ qua các phần tử trùng lặp cho conTroTrai và conTroPhai
                    while (conTroTrai < conTroPhai && danhSachSo[conTroTrai] == danhSachSo[conTroTrai + 1]) {
                        conTroTrai++;
                    }
                    while (conTroTrai < conTroPhai && danhSachSo[conTroPhai] == danhSachSo[conTroPhai - 1]) {
                        conTroPhai--;
                    }
                    // Di chuyển cả hai con trỏ vào trong để tìm bộ ba tiếp theo
                    conTroTrai++;
                    conTroPhai--;
                }
            }
        }
        return cacBoKetQua;
    }
};

18. Tổng Bốn Số

Bài toán mở rộng của "Tổng Ba Số", yêu cầu tìm tất cả các bộ bốn số nguyên (a, b, c, d) duy nhất trong một mảng danhSachSo sao cho tổng của chúng bằng một giaTriMucTieu nhất định.

Cách giải tương tự như "Tổng Ba Số", nhưng với thêm một vòng lặp ngoài. Vẫn sử dụng sắp xếp mảng và phương pháp hai con trỏ.

1. Sắp xếp mảng danhSachSo.
2. Duyệt qua mảng với con trỏ ngoài thứ nhất chiSoA (cho số a).
   • Bỏ qua các phần tử trùng lặp cho chiSoA.
   • Thêm các điều kiện tối ưu hóa để thoát sớm hoặc bỏ qua các nhánh không cần thiết:
     • Nếu tổng của 4 số nhỏ nhất có thể (từ chiSoA trở đi) đã lớn hơn giaTriMucTieu, thì không thể tìm thấy bộ bốn nào nữa, thoát vòng lặp.
     • Nếu tổng của 4 số lớn nhất có thể (từ chiSoA cùng với 3 số cuối mảng) đã nhỏ hơn giaTriMucTieu, thì số chiSoA này quá nhỏ, bỏ qua và chuyển sang chiSoA tiếp theo.
3. Bên trong vòng lặp của chiSoA, duyệt tiếp với con trỏ ngoài thứ hai chiSoB (cho số b).
   • Bỏ qua các phần tử trùng lặp cho chiSoB.
   • Tương tự, thêm các điều kiện tối ưu hóa cho chiSoB.
4. Với mỗi cặp (danhSachSo[chiSoA], danhSachSo[chiSoB]), sử dụng hai con trỏ conTroTrai (cho số c, bắt đầu từ chiSoB + 1) và conTroPhai (cho số d, bắt đầu từ cuối mảng) để tìm hai số còn lại.
5. Trong vòng lặp hai con trỏ:
   • Tính tổng currentSum = danhSachSo[chiSoA] + danhSachSo[chiSoB] + danhSachSo[conTroTrai] + danhSachSo[conTroPhai]. Sử dụng kiểu long long để tránh tràn số.
   • Điều chỉnh conTroTrai hoặc conTroPhai dựa trên so sánh currentSum với giaTriMucTieu.
   • Nếu currentSum == giaTriMucTieu, lưu bộ bốn vào kết quả và bỏ qua các phần tử trùng lặp cho conTroTrai và conTroPhai trước khi di chuyển chúng.

Mã C++ minh họa:

class Solution {
public:
    vector<vector<int>> timBonSoTongBangTarget(vector<int>& danhSachSo, int giaTriMucTieu) {
        vector<vector<int>> cacBoKetQua;
        sort(danhSachSo.begin(), danhSachSo.end()); // Sắp xếp mảng

        int n = danhSachSo.size();
        if (n < 4) return cacBoKetQua; // Cần ít nhất 4 phần tử để tạo một bộ bốn

        for (int chiSoA = 0; chiSoA < n - 3; ++chiSoA) {
            // Bỏ qua các phần tử trùng lặp cho số thứ nhất
            if (chiSoA > 0 && danhSachSo[chiSoA] == danhSachSo[chiSoA - 1]) {
                continue;
            }
            
            // Điều kiện tối ưu hóa sớm: nếu tổng của 4 số nhỏ nhất bắt đầu từ chiSoA đã lớn hơn target
            if ((long long)danhSachSo[chiSoA] + danhSachSo[chiSoA + 1] + danhSachSo[chiSoA + 2] + danhSachSo[chiSoA + 3] > giaTriMucTieu) {
                break;
            }
            // Điều kiện tối ưu hóa: nếu tổng của chiSoA và 3 số lớn nhất còn lại vẫn nhỏ hơn target
            if ((long long)danhSachSo[chiSoA] + danhSachSo[n - 3] + danhSachSo[n - 2] + danhSachSo[n - 1] < giaTriMucTieu) {
                continue;
            }


            for (int chiSoB = chiSoA + 1; chiSoB < n - 2; ++chiSoB) {
                // Bỏ qua các phần tử trùng lặp cho số thứ hai
                if (chiSoB > chiSoA + 1 && danhSachSo[chiSoB] == danhSachSo[chiSoB - 1]) {
                    continue;
                }

                // Điều kiện tối ưu hóa sớm thứ hai
                if ((long long)danhSachSo[chiSoA] + danhSachSo[chiSoB] + danhSachSo[chiSoB + 1] + danhSachSo[chiSoB + 2] > giaTriMucTieu) {
                    break;
                }
                // Điều kiện tối ưu hóa thứ hai
                if ((long long)danhSachSo[chiSoA] + danhSachSo[chiSoB] + danhSachSo[n - 2] + danhSachSo[n - 1] < giaTriMucTieu) {
                    continue;
                }

                int conTroTrai = chiSoB + 1;
                int conTroPhai = n - 1;

                while (conTroTrai < conTroPhai) {
                    long long tongHienTai = (long long)danhSachSo[chiSoA] + danhSachSo[chiSoB] + danhSachSo[conTroTrai] + danhSachSo[conTroPhai];

                    if (tongHienTai < giaTriMucTieu) {
                        conTroTrai++;
                    } else if (tongHienTai > giaTriMucTieu) {
                        conTroPhai--;
                    } else { // tongHienTai == giaTriMucTieu
                        cacBoKetQua.push_back({danhSachSo[chiSoA], danhSachSo[chiSoB], danhSachSo[conTroTrai], danhSachSo[conTroPhai]});

                        // Bỏ qua các phần tử trùng lặp cho conTroTrai và conTroPhai
                        while (conTroTrai < conTroPhai && danhSachSo[conTroTrai] == danhSachSo[conTroTrai + 1]) {
                            conTroTrai++;
                        }
                        while (conTroTrai < conTroPhai && danhSachSo[conTroPhai] == danhSachSo[conTroPhai - 1]) {
                            conTroPhai--;
                        }
                        // Di chuyển cả hai con trỏ vào trong
                        conTroTrai++;
                        conTroPhai--;
                    }
                }
            }
        }
        return cacBoKetQua;
    }
};