Bài 16 Leetcode: 3Sum Closest

Đề bài:

Cho một mảng số nguyên nums có độ dài n và một số nguyên target, tìm ba số nguyên trong nums sao cho tổng của chúng gần nhất với target. Trả về tổng của ba số nguyên đó. Bạn có thể giả định rằng mỗi đầu vào sẽ có đúng một lời giải.

Ví dụ 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Giải thích: Tổng gần nhất với target là 2. (-1 + 2 + 1 = 2).

Ví dụ 2:

Input: nums = [0,0,0], target = 1
Output: 0
Giải thích: Tổng gần nhất với target là 0. (0 + 0 + 0 = 0).

Ràng buộc:

• 3 <= độ dài của nums <= 500
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

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

class Solution {
 public:
  int threeSumClosest(vector<int>& nums, int target) {
    int ans = nums[0] + nums[1] + nums[2];

    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 == target)
          return sum;
        if (abs(sum - target) < abs(ans - target))
          ans = sum;
        if (sum < target)
          ++l;
        else
          --r;
      }
    }

    return ans;
  }
};

Đoạn mã trên triển khai thuật toán để tìm tổng gần nhất với một mục tiêu (target) từ ba số trong một mảng (nums).

1. Đầu tiên, biến ans được khởi tạo bằng tổng của ba phần tử đầu tiên trong mảng nums.

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

3. Vòng lặp for được sử dụng để duyệt qua từng phần tử của mảng nums, bắt đầu từ phần tử đầu đến hai phần tử cuối cùng (i = 0; i + 2 < nums.size(); ++i).

4. Trong vòng lặp, có một số kiểm tra điều kiện và thao tác như sau:

• – Nếu i lớn hơn 0 và giá trị của nums[i] bằng giá trị của nums[i-1], ta bỏ qua phần tử hiện tại và tiếp tục với 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 hai số còn lại trong mảng nums trong khoảng từ i+1 đến n-1 (khoảng [i+1, n-1]).

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

– Trong vòng 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 tổng sum bằng target, tức là đã tìm thấy một tổng chính xác bằng target, ta trả về giá trị sum.

+ So sánh giá trị tuyệt đối của hiệu giữa sum và target với giá trị tuyệt đối của hiệu giữa ans và target. Nếu giá trị tuyệt đối của sum và target nhỏ hơn giá trị tuyệt đối của ans và target, ta gán ans = sum.

+ Nếu tổng sum nhỏ hơn target, ta tăng vị trí l lên 1 để tìm các tổng lớn hơn.

+ Ngược lại, nếu tổng sum lớn hơn target, ta giảm vị trí r đi 1 để tìm các tổng nhỏ hơn.

6. Sau khi kết thúc vòng lặp, ta trả về giá trị của ans, tức là tổng gần nhất với target.

Thuật toán này sử dụng cách tiếp cận hai con trỏ (two-pointer approach) để tìm kiếm tổng gần nhất với target 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 gần nhất với target. Qua quá trình tìm kiếm, ta cập nhật giá trị ans để lưu giữ tổng gần nhất.

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

class Solution {
  public int threeSumClosest(int[] nums, int target) {
    int ans = nums[0] + nums[1] + nums[2];

    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 == target)
          return sum;
        if (Math.abs(sum - target) < Math.abs(ans - target))
          ans = sum;
        if (sum < target)
          ++l;
        else
          --r;
      }
    }

    return ans;
  }
}

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

class Solution:
  def threeSumClosest(self, nums: List[int], target: int) -> int:
    ans = nums[0] + nums[1] + nums[2]

    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 == target:
          return summ
        if abs(summ - target) < abs(ans - target):
          ans = summ
        if summ < target:
          l += 1
        else:
          r -= 1

    return ans