C语言三数之和的三种算法实现完整代码
时间: 2023-07-24 12:23:54 浏览: 62
好的,下面是三种不同算法实现三数之和的完整代码,均使用C语言编写:
1. 暴力枚举法
```
#include <stdio.h>
int main()
{
int nums[] = { -1, 0, 1, 2, -1, -4 };
int target = 0;
int n = sizeof(nums) / sizeof(nums[0]);
int i, j, k;
for (i = 0; i < n - 2; i++) {
for (j = i + 1; j < n - 1; j++) {
for (k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == target) {
printf("[%d %d %d]\n", nums[i], nums[j], nums[k]);
}
}
}
}
return 0;
}
```
2. 双指针法
```
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int main()
{
int nums[] = { -1, 0, 1, 2, -1, -4 };
int target = 0;
int n = sizeof(nums) / sizeof(nums[0]);
int i, j, k;
qsort(nums, n, sizeof(int), cmp);
for (i = 0; i < n - 2; i++) {
j = i + 1;
k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) {
printf("[%d %d %d]\n", nums[i], nums[j], nums[k]);
while (j < k && nums[j] == nums[j + 1]) j++;
while (j < k && nums[k] == nums[k - 1]) k--;
j++;
k--;
} else if (sum < target) {
j++;
} else {
k--;
}
}
}
return 0;
}
```
3. 哈希表法
```
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 16
typedef struct HashNode {
int key;
int val;
struct HashNode *next;
} HashNode;
typedef struct {
HashNode *head;
} HashTable;
int hash(int key)
{
return abs(key) % HASH_SIZE;
}
HashTable *createHashTable()
{
HashTable *ht = (HashTable *)malloc(HASH_SIZE * sizeof(HashTable));
for (int i = 0; i < HASH_SIZE; i++) {
ht[i].head = NULL;
}
return ht;
}
void insert(HashTable *ht, int key, int val)
{
int h = hash(key);
HashNode *p = ht[h].head;
while (p != NULL) {
if (p->key == key) {
p->val = val;
return;
}
p = p->next;
}
HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
newNode->key = key;
newNode->val = val;
newNode->next = ht[h].head;
ht[h].head = newNode;
}
int find(HashTable *ht, int key)
{
int h = hash(key);
HashNode *p = ht[h].head;
while (p != NULL) {
if (p->key == key) {
return p->val;
}
p = p->next;
}
return -1;
}
int main()
{
int nums[] = { -1, 0, 1, 2, -1, -4 };
int target = 0;
int n = sizeof(nums) / sizeof(nums[0]);
int i, j, k;
HashTable *ht = createHashTable();
for (i = 0; i < n - 2; i++) {
for (j = i + 1; j < n - 1; j++) {
int complement = target - nums[i] - nums[j];
int val = find(ht, complement);
if (val != -1 && val != i && val != j) {
printf("[%d %d %d]\n", nums[i], nums[j], complement);
}
insert(ht, nums[j], j);
}
for (j = i + 1; j < n - 1; j++) {
insert(ht, nums[j], -1);
}
}
return 0;
}
```