Leetcode题库 15.三数之和

第二次尝试结果：成功
第二次成果链接：三数之和

第一次尝试结果：失败
第一次过程如下

#include 

void Bub_Sort(int* head, int low, int high, int Bool) {
    //多次交换
    int temp; //交换
    int temp1; //优化
    for(int i = low; i < high; i++) {
        temp1 = high-(i-low);
        for(int j = low+1; j <= temp1; j++) {
            //使得head[j]始终为最值
            //Bool等于1为递增序列，Bool不等于1为递减序列
            if((head[j] < head[j-1]) == Bool) {
                temp = head[j];
                head[j] = head[j-1];
                head[j-1] = temp;
            }
        }
    }
}

void threeSum(int* nums, int numsSize) {
    // 参数初始化
    Bub_Sort(nums, 0, numsSize-1, 1); //进行顺序排序
    int head = numsSize-1; //搜索上界
    int last = 0; //搜索下界
    int seek; //搜寻子
    int last_positive_seek = head-1; //上一个正搜寻子
    int last_negative_seek =last+1; //上一个负搜寻子
    int flag; //1:搜寻子seek为目标值，0:搜寻子seek不为目标值
    int temp; //目标值存储

	// 搜索开始
    while(head-last >= 2 && nums[last]*nums[head] <= 0) {
        flag = 0;
        temp = nums[head]+nums[last]; //当前目标值：-temp
        if(temp > 0) {
            //需要搜寻一个负数
            seek = last_negative_seek; //从上一个负搜寻子开始搜索
            if(temp+nums[seek] >= 0) {
                //在last+1～last_negative_seek搜索
                for(seek; seek > last; seek--) {
                    if(temp+nums[seek] == 0) {
                        flag = 1;
                        break;
                    }
                }
            }
            else {
                //在last_negative_seek+1～最后一个负数 搜索
                while(nums[++seek] < 0) {
                    if(temp+nums[seek] == 0) {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag) {
                //负数搜索成功
                last_negative_seek = seek;
                printf("%d %d %dn", nums[head], nums[last], nums[seek]);
            }
            head--; //上界左移
            if(last_positive_seek>=head) last_positive_seek = head-1;//控制正搜索子在上界之下
        }
        else {
            //需要搜寻一个非负数
            seek = last_positive_seek; //从上一个正搜寻子开始搜索
            if(temp+nums[seek] <= 0) {
                //在last_positive_seek～head-1搜索
                for(seek; seek < head; seek++) {
                    if(temp+nums[seek] == 0) {
                        flag = 1;
                        break;
                    }
                }
            }
            else {
                //在第一个非负数～last_positive_seek-1 搜索
                while(nums[--seek] >= 0) {
                    if(temp+nums[seek] == 0) {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag) {
                //非负数搜索成功
                last_positive_seek = seek;
                printf("%d %d %dn", nums[head], nums[seek], nums[last]);
            }
            last++;//下界右移
            if(last_negative_seek<=last) last_negative_seek =last+1;//控制负搜索子在下界之上
        }
    }
}

int main() {
    int nums[15] = {
        7,7,7, 5, 3, 0, 0, 0, -1, 4, -6, -7, 2, -4, 2
    };
    threeSum(nums, sizeof(nums)/sizeof(nums[0]));
    return 0;
}