win7怎么做网站服务器吗,沙井营销型网站建设,软件开发工具属于哪种类型的软件,英孚做网络作业的网站一. 简介
本文记录一下#xff0c;力扣C语言逻辑题。主要涉及 数组方面的知识。 二. 涉及数组的 C语言逻辑题
1. 两数之和
给你一个下标从 1 开始的整数数组 numbers #xff0c;该数组已按 非递减顺序排列 #xff0c;请你从数组中找出满足相加之和等于目标数 target…一. 简介
本文记录一下力扣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 i1; 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[i1] nums[i2]) 0)break;//优化二if((nums[i] nums[numsSize-2] nums[numsSize-1]) 0)continue;j i1;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[k1]); 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[i1] nums[2]) 0)break;//优化二if((nums[i] nums[numsSize-2] nums[numsSize-1]) 0)continue;j i1;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[k1]); 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 i1; 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[i1] nums[i2]) 0)break;//优化二if((nums[i] nums[numsSize-2] nums[numsSize-1]) 0)continue;j i1;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[k1]); k--); }} }*returnSize m;return ret;
}
