Đề bài
Cho một mảng số nguyên nums, trả về tất cả các bộ ba số [nums[i], nums[j], nums[k]] sao cho i != j, i != k, và j != k, và tổng của ba số này bằng 0.
Chú ý rằng tập hợp các bộ ba phải không chứa các bộ ba trùng lặp.
Ví dụ 1:
Đầu vào: nums = [-1,0,1,2,-1,-4]
Đầu ra: [[-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 hợp lệ là [-1,0,1] và [-1,-1,2].
Ví dụ 2:
Đầu vào: nums = [0,1,1]
Đầu ra: []
Giải thích: Không có bộ ba nào có tổng bằng 0.
Ví dụ 3:
Đầu vào: nums = [0,0,0]
Đầu ra: [[0,0,0]]
Giải thích: Bộ ba duy nhất là [0,0,0].
Ràng buộc:
3 <= nums.length <= 3000
-100,000 <= nums[i] <= 100,000
Giải pháp:
Để tìm các bộ ba số có tổng bằng 0 mà không có bộ ba nào trùng lặp, ta có thể sử dụng cách tiếp cận sắp xếp và hai con trỏ.
Cách làm
#include <iostream>
#include <algorithm>
using namespace std;
void baSoCoTongBang0(int nums[], int n) {
// Sắp xếp mảng
sort(nums, nums + n);
for (int i = 0; i < n - 2; i++) {
// Bỏ qua các phần tử trùng lặp để tránh kết quả trùng lặp
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int tong = nums[i] + nums[left] + nums[right];
if (tong == 0) {
// In kết quả bộ ba hợp lệ
cout << "[" << nums[i] << "," << nums[left] << "," << nums[right] << "]" << endl;
// Bỏ qua các phần tử trùng lặp
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (tong < 0) {
left++;
} else {
right--;
}
}
}
}
int main() {
int nums[] = {-1, 0, 1, 2, -1, -4};
int n = sizeof(nums) / sizeof(nums[0]);
cout << "Cac bo ba co tong bang 0 la: " << endl;
baSoCoTongBang0(nums, n);
return 0;
}
