力扣上刷题之C语言实现-Day2

一.  简介

本文记录一下，力扣C语言逻辑题。主要涉及 数组方面的知识。

二. 涉及数组的 C语言逻辑题

1.  两数之和

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

代码实现如下：

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

实现思路：

首先，数组元素是已经递增排序好的元素。

可以从数组元素的首部 left 与尾部 right 的两个元素求和，与目标值 target进行比较。

如果 之和（首部 left 与尾部 right 的两个元素求和）大于 target值，则 尾值递减到倒数第二个元素。

如果，之和小于 targe值，则首部 left递增到第二个元素。

如果之和等于 target值，则返回两个元素的索引值。

2. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

代码实现思路：

从一个数组中找三个元素之和等于 target目标值，与 "从一个数组中找两个元素之和等于  target目标值" 的实现思路是一样的。

从数组中找三个元素之和满足条件：nums[i] + nums[j] + nums[k] == 0

（1）固定一个数组元素 nums[i]， 从数组中找两个元素之和等于 -nums[i] ，即满足如下条件：

nums[j] + nums[k] = -nums[i]。

（2）其次，上面的方法再循环遍历一遍其他数组元素。

（3）要求不能包含重复的三元组，所以，需要过滤掉重复的数。

代码实现方式一，代码实现如下：

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {int temp = 0;int i  = 0, j = 0;int k =0, m = 0;int sum = 0;int ** result = (int **)malloc((numsSize*numsSize * sizeof(int*)));*returnColumnSizes = (int *)malloc(numsSize*numsSize * sizeof(int));//从小到大排序for(i = 0; i < (numsSize-1); i++) {for(j = i+1; j < numsSize; j++) {if(nums[i] > nums[j]){temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}}//查找满足条件的三元组for(i = 0; i < numsSize-2; i++){//跳过重复的数字(nums[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-2] + nums[numsSize-1]) < 0)continue;j = i+1;k = numsSize-1;while(j < k){sum = nums[i] + nums[j] + nums[k];if(sum < 0) {j++;}else if(sum > 0) {k--;}else if(sum == 0) { //找到满足条件的三元组int* triads = (int*)malloc(3*sizeof(int));triads[0] = nums[i];triads[1] = nums[j];triads[2] = nums[k]; result[m] = triads;(*returnColumnSizes)[m++] = 3;//跳过重复的数字(nums[j])for(j++; (j < k)&& (nums[j] == nums[j-1]); j++);//跳过重复的数字(nums[k])for(k--; (j < k) && (nums[k] == nums[k+1]); k--);      }}   }*returnSize = m;return result;
}

代码实现方式二，代码实现如下：

int compare(const void *a, const void *b) {return (*(int*)a - *(int*)b);
}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {int temp = 0;int i  = 0, j = 0;int k =0, m = 0;int sum = 0;int ** result = (int **)malloc((numsSize*numsSize * sizeof(int*)));*returnColumnSizes = (int *)malloc(numsSize*numsSize * sizeof(int));//sort from smallest to largestqsort(nums, numsSize, sizeof(int), compare);//查找满足条件的三元组for(i = 0; i < numsSize-2; i++){//跳过重复的数字(nums[i]）if((i > 0) && (nums[i] == nums[i-1])) {continue;}//优化一if((nums[i] + nums[i+1] +nums[2]) > 0)break;//优化二if((nums[i] + nums[numsSize-2] + nums[numsSize-1]) < 0)continue;j = i+1;k = numsSize-1;while(j < k){sum = nums[i] + nums[j] + nums[k];if(sum < 0) {j++;}else if(sum > 0) {k--;}else if(sum == 0) { //找到满足条件的三元组int* triads = (int*)malloc(3*sizeof(int));triads[0] = nums[i];triads[1] = nums[j];triads[2] = nums[k]; result[m] = triads;(*returnColumnSizes)[m++] = 3;//跳过重复的数字(nums[j])for(j++; (j < k)&& (nums[j] == nums[j-1]); j++);//跳过重复的数字(nums[k])for(k--; (j < k) && (nums[k] == nums[k+1]); k--);      }}}*returnSize = m;return result;
}

另外一种接口封装方式，代码实现如下：

int threeSum(int* nums, int numsSize, int* returnSize, int* ret_buf) {int temp = 0;int i  = 0, j = 0;int k = 0, m = 0;int sum = 0;int ret = -1;//从小到大排序for(i = 0; i < (numsSize-1); i++) {for(j = i+1; j < numsSize; j++) {if(nums[i] > nums[j]){temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}}//查找满足条件的三元组for(i = 0; i < numsSize-2; i++){//跳过重复的数字(nums[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-2] + nums[numsSize-1]) < 0)continue;j = i+1;k = numsSize-1;while(j < k){sum = nums[i] + nums[j] + nums[k];if(sum < 0) {j++;}else if(sum > 0) {k--;}else if(sum == 0) { //找到满足条件的三元组ret_buf[m++] = nums[i];ret_buf[m++] = nums[j];ret_buf[m++] = nums[k]; ret = 0;//跳过重复的数字(nums[j])for(j++; (j < k)&& (nums[j] == nums[j-1]); j++);//跳过重复的数字(nums[k])for(k--; (j < k) && (nums[k] == nums[k+1]); k--);      }}   }*returnSize = m;return ret;
}