https://leetcode.com/problems/3sum/
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: 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. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
#include <stdlib.h>
// Hàm so sánh để sắp xếp mảng
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
// Khởi tạo kết quả
int **result = malloc(sizeof(int*) * numsSize * numsSize); // Lưu các bộ ba
*returnColumnSizes = malloc(sizeof(int) * numsSize * numsSize); // Lưu số cột của mỗi dòng
*returnSize = 0; // Số lượng bộ ba tìm được
// Sắp xếp mảng để dễ xử lý
qsort(nums, numsSize, sizeof(int), compare);
// Duyệt qua từng phần tử làm gốc
for (int i = 0; i < numsSize - 2; i++) {
// Bỏ qua các phần tử trùng lặp
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1; // Chỉ số trái
int right = numsSize - 1; // Chỉ số phải
// Tìm bộ ba có tổng bằng 0
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// Lưu bộ ba hợp lệ
result[*returnSize] = malloc(sizeof(int) * 3);
result[*returnSize][0] = nums[i];
result[*returnSize][1] = nums[left];
result[*returnSize][2] = nums[right];
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
// 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--;
// Di chuyển con trỏ
left++;
right--;
} else if (sum < 0) {
left++; // Tăng giá trị tổng
} else {
right--; // Giảm giá trị tổng
}
}
}
return result;
}