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