力扣刷题（6）

两数之和 II - 输入有序数组

两数之和 II - 输入有序数组-力扣

思路：

1. 因为该数组是非递减顺序排列，因此可以设两个左右下标
2. 当左右下标的数相加大于target时，则表示右下标的数字过大，因此将右下标 - -
3. 当左右下标的数相加小于target时，则表示左下标的数字过小，因此将左下标 + +
4. 当相等时，则将左右下标赋值给动态开辟的数组，并返回（注意左右下标要+1）

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int* ret=(int*)malloc(sizeof(int)*2);
    *returnSize=2;
    int left =0,right=numbersSize-1;
    while(left < right)
    {
        if(numbers[left] + numbers[right] == target)
        {
            ret[0]=left+1;
            ret[1]=right+1;
            return ret;
        }
        else if(numbers[left] + numbers[right] > target)
        {
            right--;
        }
        else
        {
            left++;
        }
    }
    return ret;
}

三数之和

三数之和-力扣

思路来源：灵茶山艾府

1. 将数组进行排序
2. 将三个数分为两组，第一个数一组，第二三个数的和分为一组，这样思路就和上一题的两数相加相同了
3. 当第一个数存在重复时，需要continue从而跳到最后一个重复的数
4. 再对后两个数进行判断，思路同第一题

这题存在两个能够进行优化的地方：

1. 当三个连续数字相加大于0时，则不存在和为0的数字，可以直接break退出循环（因为数组是有序的）
2. 当一个数和最后两个最大的数字之和小于0，则该数字不可能存在为0的情况，直接continue进入下一个数字的判断即可

int cmp(const void* a, const void* b)
 {
    return *(int*)a-*(int*)b;
 }

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums,numsSize,sizeof(int),cmp);
    int** ret=(int**)malloc(sizeof(int*)*numsSize*numsSize);
    *returnColumnSizes=(int*)malloc(sizeof(int)*numsSize*numsSize);
    int m=0;
    for(int i=0;i<numsSize-2;i++)
    {
    	//跳过重复数字
        if(i > 0 && nums[i] == nums[i-1])
            continue;
        if(nums[i] + nums[i+1] + nums[i+2] > 0)
            break;//优化一
        if(nums[i] + nums[numsSize-1] + nums[numsSize-2] < 0)
            continue;//优化二
        int j=i+1;
        int k=numsSize-1;
        while(j < k)
        {
            if(nums[i] + nums[j] + nums[k] > 0)
                k--;
            else if(nums[i] + nums[j] + nums[k] < 0)
                j++;
            else
            {
            	//添加三元组
                int* arr=(int*)malloc(sizeof(int)*3);
                arr[0]=nums[i];
                arr[1]=nums[j];
                arr[2]=nums[k];
                ret[m]=arr;
                (*returnColumnSizes)[m++]=3;
                //跳过重复数字
                for(j++;j < k && nums[j] == nums[j-1];j++);
                for(k--;k > j && nums[k] == nums[k+1];k--);
            }
        }
    }
    *returnSize=m;
    return ret;
}

最接近的三数之和

最接近的三数之和-力扣

思路同第二题类似

int cmp(const void* a,const void* b) 
{
    return *(int*)a-*(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target) {
    qsort(nums,numsSize,sizeof(int),cmp);
    int sum=nums[0]+nums[1]+nums[2];
    for(int i=0;i<numsSize-2;i++)
    {
        int j=i+1;
        int k=numsSize-1;
        while(j < k)
        {
            int tmp=nums[i]+nums[j]+nums[k];
            if(abs(tmp-target) < abs(sum-target))
                sum=tmp;
            if(tmp > target)
                k--;
            else if(tmp < target)
                j++;
            else
                return sum;
        }
    }
    return sum;
}