(-1 2 1 2) - bảng tỷ số bóng đá
]( "Giới thiệu bài toán") Giới thiệu bài toán
Cho một mảng số nguyên nums có độ dài n và một số nguyên target, hãy tìm ba số trong mảng nums sao cho tổng của chúng gần với target nhất.
Trả về tổng của ba số nguyên đó.
Bạn có thể giả sử rằng mỗi đầu vào sẽ có đúng một giải pháp.
Tóm lại, trước đây chúng ta cần tìm ba số có tổng bằng giá trị mục bảng tỷ số bóng đá tiêu, nhưng bây giờ chúng ta chỉ cần tìm ba số có tổng gần nhất với giá trị mục tiêu.
[Ví dụ]
[]( "Ví dụ 1:") Ví dụ 1:
Đầu vào: nums = [-1,2,1,-4], target = 1
Đầu ra: 2
Giải thích: Tổng gần nhất với mục tiêu là 2. (-1 + 2 + 1 = 2).
[]( "Ví dụ 2:") Ví dụ 2:
Đầu vào: nums = [0,0,0], target = 1
Đầu ra: 0
[]( "Ràng buộc:") Ràng buộc:
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-10^4 <= target <= 10^4
]( "Phân loc.club - cổng game quốc tế tích đơn giản") Phân tích đơn giản
Bài toán này không quá phức tạp về mặt tư duy. Chúng ta áp dụng phương pháp từng được sử dụng trong bài toán tổng ba số bằng cách sử dụng kỹ thuật "hai con trỏ" hoặc các phương pháp tương tự. Tuy nhiên, ở đây chúng ta cần tối ưu hóa logic để tìm ra kết quả gần nhất thay vì chính xác.
[Mã nguồn]
1public int threeSumClosest(int[] nums, int target) {
2 // Sắp xếp mảng đầu vào
3 Arrays.sort(nums);
4
5 // Khởi tạo tổng gần nhất ban đầu
6 int closestSum = nums[0] + nums[1] + nums[nums.length - 1];
7
8 // Duyệt qua từng phần tử trong mảng
9 for (int i = 0; i < nums.length - 2; i++) {
10 if (i == 0 || nums[i] != nums[i - 1]) {
11 // Xác định hai con trỏ
12 int left = i + 1;
13 int right = nums.length - 1;
14
15 // Thực hiện kiểm tra khi hai con trỏ chưa gặp nhau
16 while (left < right) {
17 // Tính tổng hiện tại
18 int sum = nums[i] + nums[left] + nums[right];
19
20 // Loại bỏ các phần tử trùng lặp
21 while (left < right && nums[left] == nums[left + 1]) {
22 left++;
23 }
24 while (left < right && nums[right] == nums[right - 1]) {
25 right--;
26 }
27
28 // Điều chỉnh con trỏ dựa trên giá trị tổng
29 if (sum < target) {
30 left++;
31 } else {
32 right--;
33 }
34
35 // Cập nhật tổng gần nhất nếu cần thiết
36 if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
37 closestSum = sum;
38 }
39 }
40 }
41 }
42 return closestSum;
43}