兩數之和 - 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 運行的提示

看提示是指針導致的問題，不過我還沒有什麼解決的方法，也不是很確定錯在了哪裡，大家如果發現了我哪裡錯了的麻煩留個言哈，謝謝啦