两数之和 - ekko

描述#

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路#

申请内存
固定第一个下标，查找是否有满足条件的第二个下标
找到两个符合的下标，返回

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
        *returnSize = 2;
        int* values = (int*)malloc(sizeof(int) * (*returnSize));
        for(values[0] = 0;values[0] < numsSize ;values[0]++) {
            for(values[1] = values[0] + 1;values[1] < numsSize ;values[1]++) {
                if(nums[values[0]] + nums[values[1]] == target) {
                    return values;
                }  
            }
        }
        return 0;

}

刚开始的时候看到形参中的returnSize, 以为不是两数之和，而是给定的某数之和，所以要实现 n 个 for 循环，但没有合理规律的思路，因为一时没想到 n 个 for 循环应该怎样写出来

然后看了下网上的解法，是直接默认returnSize是 2 的，因此就不纠结直接用上述方法暴力搜索，目前还未想到新的方式来解决

N 数之和#

不过写出这个解法后，发现这两个 for 循环是有规律的，因此实现 n 数之和貌似也有了思路，需要用到递归算法

int digui(int* nums, int numsSize, int target, int* returnSize,int i,int sum,int* values,int* flag) {
    //退出条件
    if(*flag == 1)
        return 0;
    //first time
    if(i == 0) {
        for(values[0] = 0;values[0] < numsSize ;values[0]++) {
            sum += nums[values[0]];
            digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
        }
    }
    //another time
    else {
        for(values[i] = values[i-1] + 1;values[i] < numsSize ;values[i]++) {
            sum += nums[values[i]];
            //last time
            if(i == *returnSize - 1) {
                if(sum == target)
                    *flag = 1;
                return 0;
            }
            //not last time
            else
                digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
        }
    } 
    return 0;
}

形参中相比于原来，多了四个参数，i: 表面当前处于嵌套第几层，sum：前几层嵌套的和，value: 存放下标地址，flag: 结束标志。递归结束条件是最后第 n 个数时，总和达到要求，下面是调试用的代码

#include <stdio.h>
#include <malloc.h>
int digui(int* nums, int numsSize, int target, int* returnSize,int i,int sum,int* values,int* flag);
int digui(int* nums, int numsSize, int target, int* returnSize,int i,int sum,int* values,int* flag) {
    //退出条件
    if(*flag == 1)
        return 0;
    //first time
    if(i == 0) {
        for(values[0] = 0;values[0] < numsSize ;values[0]++) {
            sum += nums[values[0]];
            digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
        }
    }
    //another time
    else {
        for(values[i] = values[i-1] + 1;values[i] < numsSize ;values[i]++) {
            sum += nums[values[i]];
            //last time
            if(i == *returnSize - 1) {
                if(sum == target)
                    *flag = 1;
                return 0;
            }
            //not last time
            else
                digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
        }
    } 
    return 0;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nSum(int* nums, int numsSize, int target, int* returnSize){
    int* values = (int*)malloc(sizeof(int) * (*returnSize));
    static int sum = 0,i = 0,flag = 0;
    digui(nums,numsSize,target,returnSize,0,sum,values,&flag);
    return values;
}

int main(void) {
    static int nums[7] = {8,12,34,2,3,5,33};
    static int target = 10;
    static int numsSize = 7;
    static int returnSize = 3;
    int* value = nSum(nums,numsSize,target,&returnSize);
    printf("value are %d %d %d\n",value[0],value[1],value[2]);
    free(value);
    return 0;
}

不过在编译运行的时候遇到了错误，下面是 gdb 运行的提示

看提示是指针导致的问题，不过我还没有什么解决的方法，也不是很确定错在了哪里，大家如果发现了我哪里错了的麻烦留个言哈，谢谢啦