描述#
整数配列 nums と目標値 target が与えられた場合、配列内の目標値となる 2 つの 整数を見つけ、それらのインデックスを返します。
入力は 1 つの答えに対して 1 つの結果しかないことを前提としていますが、配列内の同じ要素を再利用することはできません。
例:
nums = [2, 7, 11, 15]、target = 9 の場合、
nums[0] + nums[1] = 2 + 7 = 9 なので、[0, 1] を返します。
思路#
- メモリを割り当てる
- 最初のインデックスを固定し、条件を満たす 2 番目のインデックスを探す
- 2 つの条件を満たすインデックスを見つけたら、それを返す
/**
* 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を見て、2 つの数の和ではなく、与えられた数の和を考えてしまいましたので、n 個の for ループを実現するためにはどのように書けばいいのか、合理的なアプローチが思い浮かびませんでした。
その後、オンラインの解法を見て、returnSizeを 2 としてデフォルト値に設定していることに気づき、上記の方法で総当たり検索を行いましたが、まだ新しい方法を見つけることができませんでした。
N 数の和#
ただし、この解法を書いた後、これらの 2 つの 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;
//最初の場合
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);
}
}
//他の場合
else {
for(values[i] = values[i-1] + 1;values[i] < numsSize ;values[i]++) {
sum += nums[values[i]];
//最後の場合
if(i == *returnSize - 1) {
if(sum == target)
*flag = 1;
return 0;
}
//最後の場合でない場合
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;
//最初の場合
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);
}
}
//他の場合
else {
for(values[i] = values[i-1] + 1;values[i] < numsSize ;values[i]++) {
sum += nums[values[i]];
//最後の場合
if(i == *returnSize - 1) {
if(sum == target)
*flag = 1;
return 0;
}
//最後の場合でない場合
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 の実行時のメッセージです。
エラーメッセージによると、ポインタの問題が原因のようですが、どこが間違っているのかはまだ確信が持てません。もし私のどこかが間違っていると気づいたら、コメントを残していただけると助かります。ありがとうございます。