三数之和为0（c语言实现）（改进）

暴力枚举：暴力枚举算法

改进算法：
主要函数
QS（）：由小到大快速排序
SearLR（）：寻找最大的负数以及最小的正数并返回
Seekaim（）：折半查找
Classify（）：分别寻找三零、一零、无零并输出
Small_artillery（）：去重
threeSum（）：排除两端为零
main（）：入口函数

#include <stdio.h>
void QS(int *nums, int low, int high) {
//需排序的片段首位序号
if(high > low) {
int low1 = low, high1 = high, flag = nums[low], temp;
while(high1 > low1) {
while(high1 > low1 && nums[high1] >= flag) high1--;
nums[low1] = nums[high1];
while(high1 > low1 && nums[low1] < flag) low1++;
nums[high1] = nums[low1];
}
nums[low1] = flag;
QS(nums, low, low1-1);
QS(nums, low1+1, high);
}
}
void SearLR(int* nums, int numsSize, int* retl, int* retr) {
//最大的负数 and 最小的正数
for(int i = 0; i < 6; i++) {
}
*retl = -1;
*retr = numsSize;
for(int i = 0; i < numsSize-1; i++) {
if(nums[i] < 0) *retl = i;
if(nums[numsSize-1-i] > 0) *retr = numsSize-1-i;
}
}
int Seekaim(int* nums, int aim, int left, int right) {
//在[l，r]搜寻aim的位置,-1:不存在
if(nums[left] <= aim && aim <= nums[right]) {
while(left < right) {
if(nums[(left+right)/2] < aim) {
left = (left+right)/2+1;
}else {
right = (left+right)/2;
}
}
}
return nums[left] == aim?left: -1;
}
//按照三元组中0的个数（Num0）分类
//返回[n][3]
void Classify(int* nums, int numsSize, int left, int right) {
//寻找三零
int z0;
if(right-left>=4){printf("n三零:%d %d %d", 0, 0, 0);}
else{printf("n三零：没有");}
printf("n");
//寻找一零
if(right-left>=2){
int i = 0, z = numsSize-1;
while(i <= left) {
z0=Seekaim(nums, -nums[i], right, z);
if(z0 != -1) {
z = z0;
printf("n一零：%d %d %d", 0, nums[i], -nums[i]);
}
i++;
}
}else{printf("n一零：没有");}
printf("n");
//寻找无零
int x = 0;
while(x <= left) {
int y = right,z = numsSize,z1=-1;
while(y <= numsSize-1) {
if(nums[x]+nums[y] > 0) {
if(z>left) {
z = left;
}
z0=Seekaim(nums, -(nums[x]+nums[y]), 0, z);
if(z0 != -1) {
z = z0;
printf("n无零：%d %d %d", nums[x], nums[y], -(nums[x]+nums[y]));
break;
}
}
else {
if(z1<right){
z1=numsSize;
}
z0=Seekaim(nums, -(nums[x]+nums[y]), y, z1);
if(z0 != -1) {
z1 = z0;
printf("n无零：%d %d %d", nums[x], nums[y], -(nums[x]+nums[y]));
break;
}
}
y++;
}
x++;
}
}
void Small_artillery(int* nums, int numsSize, int left, int right) {//判断L、R中间0的个数；以无0、一个0，三个0分类
int flag=10^5+1,i=0,j=0;
while(i<numsSize || nums[i]==0){
if(nums[i]!=nums[j]){
j++;
nums[j]=nums[i];
}
i++;
}
numsSize=j+1;
SearLR(nums, numsSize, &left, &right);
Classify(nums,numsSize,left,right);
}
void threeSum(int* nums, int numsSize) {
int** returnColumnSizes[10000][3], flag = -1;
if(numsSize > 2) {
QS(nums, 0, numsSize-1);
int left, right;
SearLR(nums, numsSize, &left, &right); //最大的负数 and 最小的正数
if(left == -1 || right == numsSize) {
//左边界为0 or 右边界为0
if(right-left >= 4) {
printf("n三零:%d %d %d", 0, 0, 0);
flag++;
}else {
printf("n没有");
}
}else {
//排除边界为0;判断L、R中间0的个数；以无0、一个0，三个0分类
Small_artillery(nums, numsSize, left, right);
}
}else {
printf("n没有");
}
}
int main(int argc, char **argv) {
int nums[100] = {0,7,-4,-7,0,14,-6,-4,-12,11,4,9,7,4,-10,8,10,5,4,14,6,0,-9,5,6,6,-11,1,-8,-1,2,-1,13,5,-1,-2,4,9,9,-1,-3,-1,-7,11,10,-2,-4,5,10,-15,-4,-6,-8,2,14,13,-7,11,-9,-8,-13,0,-1,-15,-10,13,-2,1,-1,-15,7,3,-9,7,-1,-14,-10,2,6,8,-6,-12,-13,1,-3,8,-9,-2,4,-2,-3,6,5,11,6,11,10,12,-11,-14};
threeSum(nums,100);
return 0;
}

最后

以上就是勤恳草丛为你收集整理的三数之和为0（c语言实现）（改进）的全部内容，希望文章能够帮你解决三数之和为0（c语言实现）（改进）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。