一. 简介
本文记录一下,力扣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;
}