1. 题目描述
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
2. 解题思路
详见代码注释，时间复杂度为O(n^2)。
3. 完整代码
#include <stdio.h>#include <malloc.h>int factorial(int n); //求一个数的阶乘bool bS3Exist(int* s3[3], int len, int i1, int i2, int i3); //判断三元组是否重复，如果三个数完全一样则为重复int main(){ int* S = NULL; //存储数组 int* S3[3] = { 0 }; //存储所有的三元组 int n = 0; int num = 0; PRintf("请输入数组的长度：/n"); scanf("%d", &n); if (n< 3) { printf("长度必须大于等于3，请重新输入：/n"); scanf("%d", &n); } S = (int*)malloc(sizeof(int) * n); //数组分配内存 if (n == 3) num = 1; //只有一种情况,带入公式分母为0 else num = factorial(n) / (factorial(3) * factorial(n - 3)); //根据组合公式，求出所有3元组的个数 printf("组合数：%d/n", num); S3[0] = (int *)malloc(sizeof(int) * num); //分配二维数组 S3[1] = (int *)malloc(sizeof(int) * num); //分配二维数组 S3[2] = (int *)malloc(sizeof(int) * num); //分配二维数组 printf("请输入数组的每一位数：/n"); for (int i = 0; i<n; ++i) { scanf("%d", &S[i]); } for (int i = 0; i< num; i++) { for (int j = 0; j< 3; j++) { S3[j][i] = 0; } } for (int i = 0; i<n; ++i) { printf("%d ", S[i]); } printf("/n "); num = 0; int temp1 = 0; int temp2 = 0; int temp3 = 0; int i1 = 0; int i2 = 0; int i3 = 0; for (int i1 = 0; i1 < n - 2; ++i1) //取出数列中的全部不重复的三元组合 { i2 = i1 + 1; for (; i2< n - 1; ++i2) { i3 = i2 + 1; for (; i3 < n; ++i3) { if (!bS3Exist(S3, num, S[i1], S[i2], S[i3])) //判断是否重复 { printf("[i1:%d=%d i2:%d=%d i3:%d=%d]/n", i1, S[i1], i2, S[i2], i3, S[i3]); temp1 = S[i1]; temp2 = S[i2]; temp3 = S[i3]; S3[0][num] = temp1; S3[1][num] = temp2; S3[2][num] = temp3; num += 1; } } } } printf("组合数：%d/n", num); int* Sn = (int*)malloc(sizeof(int) * num); //定义一个数组来存储符合条件的三元组序号 for (int i = 0; i< num; ++i) { Sn[i] = -1; } for (int i = 0; i< num; ++i) //判断哪些三元组是符合条件的 { int sum = S3[0][i] + S3[1][i] + S3[2][i]; printf("[%d %d %d]/n", S3[0][i], S3[1][i], S3[2][i]); if (sum == 0) { Sn[i] = 1; } } //输出结果 printf("所有和为0的三元组如下:/n"); for (int i = 0; i< num; ++i) { if (Sn[i] == 1) { printf("[%d %d %d]/n", S3[0][i], S3[1][i], S3[2][i]); } } scanf("%d", &n); //加个输入让窗口停下来 free(S); return 0;}int factorial(int n){ int sum = 1; if (1 == n) { return 1; } sum = n * factorial(n - 1); return sum;}bool bS3Exist(int* s3[3], int len, int i1, int i2, int i3){ for (int i = 0; i< len; ++i) { int a = s3[0][i]; int b = s3[1][i]; int c = s3[2][i]; if ((a == i1 && b == i2 && c == i3) || (a == i1 && b == i3 && c == i2) || (a == i2 && b == i1 && c == i3) || (a == i2 && b == i3 && c == i1) || (a == i3 && b == i1 && c == i2) || (a == i3 && b == i2 && c == i1)) { return true; } } return false;}新闻热点
疑难解答
