Bài 15 Leetcode: 3Sum

Đề bài:

Cho một mảng số nguyên nums, trả về tất cả các bộ ba [nums[i], nums[j], nums[k]] sao cho i != j, i != k, j != k và nums[i] + nums[j] + nums[k] == 0.

Lưu ý rằng tập hợp các bộ ba kết quả không được chứa các bộ ba trùng lặp.

Ví dụ 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Giải thích: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
Các bộ ba khác nhau là [-1,0,1] và [-1,-1,2].
Lưu ý rằng thứ tự của kết quả và thứ tự các bộ ba không quan trọng.

Ví dụ 2:

Input: nums = [0,1,1]
Output: []
Giải thích: Chỉ có một bộ ba có thể có, nhưng không tổng lại thành 0.

Ví dụ 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Giải thích: Chỉ có một bộ ba có thể có và tổng của nó là 0.

Ràng buộc:

• 3 <= độ dài của nums <= 3000
• -10^5 <= nums[i] <= 10^5

Giải thích thuật toán bằng C++

class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    if (nums.size() < 3)
      return {};

    vector<vector<int>> ans;

    ranges::sort(nums);

    for (int i = 0; i + 2 < nums.size(); ++i) {
      if (i > 0 && nums[i] == nums[i - 1])
        continue;
      // Choose nums[i] as the first num in the triplet,
      // and search the remaining nums in [i + 1, n - 1]
      int l = i + 1;
      int r = nums.size() - 1;
      while (l < r) {
        const int sum = nums[i] + nums[l] + nums[r];
        if (sum == 0) {
          ans.push_back({nums[i], nums[l++], nums[r--]});
          while (l < r && nums[l] == nums[l - 1])
            ++l;
          while (l < r && nums[r] == nums[r + 1])
            --r;
        } else if (sum < 0) {
          ++l;
        } else {
          --r;
        }
      }
    }

    return ans;
  }
};

Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm threeSum(vector<int>& nums) theo thuật toán đã mô tả trước đó. Dưới đây là giải thích chi tiết về thuật toán này:

1. Hàm threeSum(vector<int>& nums): Đây là hàm chính để tìm tất cả các bộ ba số [nums[i], nums[j], nums[k]] từ một mảng số nguyên nums. Hàm này nhận đầu vào là một vector nums chứa các số nguyên.

2. Kiểm tra nếu độ dài của nums nhỏ hơn 3, tức là không đủ số để tạo thành bộ ba, ta trả về một vector rỗng {}.

3. Khai báo một vector 2 chiều ans để lưu kết quả cuối cùng.

4. Sắp xếp mảng nums theo thứ tự tăng dần bằng cách sử dụng hàm sort().

5. Sử dụng vòng lặp for để duyệt qua từng phần tử của nums từ đầu đến trước 2 phần tử cuối cùng (i = 0; i + 2 < nums.size(); ++i):

– Trong vòng lặp, ta kiểm tra các trường hợp sau:

+ Nếu i lớn hơn 0 và nums[i] bằng nums[i – 1], ta bỏ qua phần tử hiện tại và chuyển đến phần tử tiếp theo để tránh các bộ ba trùng lặp.

+ Chọn nums[i] làm số đầu tiên trong bộ ba và tìm kiếm các số còn lại trong mảng nums trong khoảng từ i + 1 đến n – 1 (làm số thứ hai và số thứ ba trong bộ ba).

6. Sử dụng hai con trỏ l và r để biểu diễn đầu và cuối của một cặp số con trong mảng nums.

– Lặp while (l < r) để tiến hành tìm kiếm.

– Tính tổng của ba số hiện tại: sum = nums[i] + nums[l] + nums[r].

+ Nếu sum = 0, tức là tìm thấy một bộ ba số thỏa mãn, ta thêm bộ ba này vào vector ans. Tiếp theo, ta tăng lên 1 đơn vị và giảm r đi 1 đơn vị để tiếp tục tìm kiếm các bộ ba khác.

•  Trong quá trình này, ta cũng kiểm tra và bỏ qua các phần tử trùng lặp bằng cách so sánh với các phần tử trước đó. (nums[l] == nums[l – 1] và nums[r] == nums[r + 1])

+ Nếu sum < 0, tức là tổng hiện tại quá nhỏ, ta tăng lên 1 đơn vị l để tìm các tổng lớn hơn.

+ Nếu sum > 0, tức là tổng hiện tại quá lớn, ta giảm r đi 1 đơn vị để tìm các tổng nhỏ hơn.

7. Sau khi kết thúc vòng lặp, ta trả về vector ans chứa tất cả các bộ ba số thỏa mãn yêu cầu.

Thuật toán này sử dụng cách tiếp cận hai con trỏ để tìm kiếm các bộ ba số có tổng bằng 0 trong mảng nums. Bằng cách sắp xếp mảng và duyệt qua từng phần tử, ta chọn số đầu tiên trong bộ ba và tìm hai số còn lại để tổng của bộ ba bằng 0. Qua quá trình tìm kiếmLưu ý: Trong đoạn mã trên, có một số thư viện và cú pháp cụ thể của ngôn ngữ C++ được sử dụng.

Giải thích thuật toán bằng Java

class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
    if (nums.length < 3)
      return new ArrayList<>();

    List<List<Integer>> ans = new ArrayList<>();

    Arrays.sort(nums);

    for (int i = 0; i + 2 < nums.length; ++i) {
      if (i > 0 && nums[i] == nums[i - 1])
        continue;
      // Choose nums[i] as the first number in the triplet, then search the
      // remaining numbers in [i + 1, n - 1].
      int l = i + 1;
      int r = nums.length - 1;
      while (l < r) {
        final int sum = nums[i] + nums[l] + nums[r];
        if (sum == 0) {
          ans.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
          while (l < r && nums[l] == nums[l - 1])
            ++l;
          while (l < r && nums[r] == nums[r + 1])
            --r;
        } else if (sum < 0) {
          ++l;
        } else {
          --r;
        }
      }
    }

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    if len(nums) < 3:
      return []

    ans = []

    nums.sort()

    for i in range(len(nums) - 2):
      if i > 0 and nums[i] == nums[i - 1]:
        continue
      # Choose nums[i] as the first number in the triplet, then search the
      # remaining numbers in [i + 1, n - 1].
      l = i + 1
      r = len(nums) - 1
      while l < r:
        summ = nums[i] + nums[l] + nums[r]
        if summ == 0:
          ans.append((nums[i], nums[l], nums[r]))
          l += 1
          r -= 1
          while nums[l] == nums[l - 1] and l < r:
            l += 1
          while nums[r] == nums[r + 1] and l < r:
            r -= 1
        elif summ < 0:
          l += 1
        else:
          r -= 1

    return ans