（準備中）
2つの数の和の問題を解くプログラムについて考えてみます。
最初にいくつかの整数と目標とする合計値（整数）が与えられ、最初に与えられた整数の中から2つの整数を選んで
目標の合計値を作るというのが、2つの数の和の問題です。
LeetCodeの最初の問題(TwoSum）もこの問題です。
LeetCodeでは、最初の整数は配列で与えられ、合計値を作る2つの整数の配列番号（配列の添え字）を回答として
returnする関数を作るという問題になっています。
例えば、最初に与えられる整数の配列が [1, 5, 10,20]で、求める合計値が25であった場合、
回答は[1,3]になります。
Leetcodeでは、制約として
最初に与えられる整数の個数は、2〜104、整数の値は-109〜109、目標となる合計値も-109〜109 と
が付けられています。
LeetCodeのTwoSum問題は、それらの整数を与えられて回答をrerurnする関数の部分だけを作る問題ですが、
ここでは、所定の配列が与えられるのではなく、コンソールから整数を入力して与える形式とし、
最初の数値の入力をする部分（main関数）含めて全体のプログラムを作ることにします。
このプログラムを作るだけでもCの様々な仕様を学習することになります。
（１） 関数化しない（mainに全て書く）
最初は2つの数の和を求めるコードの部分を関数化せずに、main()の中で全て完結してしまう
プログラムです。
最初に入力する整数の数を入力させ、nsizeに格納します。
次にnsizeの回数分forループを回して整数を入力します。 整数値はn[]に保存します。
このプログラムではn[20]と宣言しており、入力できる整数値は20個までです。ただし、細かな入力チェックは
してません。
最後に求める合計値を入力させtargetに保存します。
ret[0],ret[1]に合計値に合致した時の2つの整数の番号（n[]の配列の添え字）を格納することとし、
初期値はret[0]=-1,ret[1]=-1としておきます。
for文による二重ループで合計値になる2つの整数値があるかチェックします。
合致する整数値が見つかった時は、goto文で一気に二重ループを飛び出します。
ret[0]==-1の時は、合計値に合致するような2つの整数値はなかったということなので、
No pair numberと表示します。
<TwoSumN.c>
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n[20],i,j,nsize,target,ret[2];
printf("number of input data:");
scanf("%d",&nsize);
printf("data:");
for (i=0;i<nsize;i++){scanf("%d",&n[i]);}
printf("target:");
scanf("%d",&target);
ret[0]=-1;ret[1]=-1;
for (i=0;i<nsize;i++)
{
for(j=i+1;j<nsize;j++) {
if ((n[i]+n[j])==target) {ret[0]=i;ret[1]=j;goto L1;}
}
}
L1:
if (ret[0] == -1) printf("No pair number\n");
else printf("result:%d, %d because %d + %d", ret[0], ret[1],n[ret[0]],n[ret[1]]);
return 0;
}
実行例（Borland C++55でコンパイル）
（２） 関数化してみる
2つの数の和を求めるコードの部分を関数化してみます。
二重forループで合計値に合致する2つの整数値を求める部分をtwosumという関数にしてみます。
twosumに渡す引数は以下の通りです。
numsize 整数値の個数（整数の配列の要素の個数）
*num 整数値の配列
target 合計値
二重forループでやっていることは(1)と同じです。
main関数から呼ぶ呼び出し元は
ret=twosum(nsize,n,t);
としています。
twosumはポインタをreturnする関数です。
twosum関数からは、return ret; でretのポインタを返します。
ret[0], ret[1]には合計値に合致したときの配列の番号（添え字）を入れていますので、
main関数のほうのretでもret[0],ret[1]でその配列の番号を受け取ることができます。
Cで複数の値を受け渡しする方法のひとつがポインタをreturnする方法になります。
retは関数の中のローカルのポインタ変数なので、retのための領域をmallocで確保しています・
呼び出し元（main）でこの領域はfree()で解放します。
mallocで領域確保する理由は関数の引数と返値に説明がありますので、ご参照下さい。
ただし、このTwoSum2.1.cはLeetCodeの問題に出てくる関数とは少し違います。
<TwoSum2.1.c>
#include <stdio.h>
#include <stdlib.h>
int* twosum();
int* twosum(int numsize, int * num, int target){
int i,j,*ret;
ret=(int*)malloc(2*(sizeof(int))); //メモリの確保
ret[0]=-1;ret[1]=-1;
for (i=0;i<numsize;i++)
{
for(j=i+1;j<numsize;j++) {
if (i==j) continue;
if ((num[i]+num[j])==target) {ret[0]=i;ret[1]=j;return ret;}
}
}
return ret;}
int main(void)
{
int n[20],i,nsize,t,*ret;
printf("number of input data:");
scanf("%d",&nsize);
printf("data:");
for (i=0;i<nsize;i++){scanf("%d",&n[i]);}
printf("target:");
scanf("%d",&t);
ret=twosum(nsize,n,t);
if (ret != NULL) {
if (ret[0] == -1){ printf("No pair number\n");}
else {printf("result:%d, %d because %d + %d", ret[0], ret[1],n[ret[0]],n[ret[1]]);}
free(ret); //メモリ開放
}
return 0;
}
（３） LeetCodeの問題と同じ関数にしてみる
LeetCodeの問題ではCのプログラムの関数は引数を4つ取る関数になっています。
次はLeetCodeの問題に合わせた関数でプログラムを書いてみます。
LeetCodeのTwoSum問題では、twoSum関数は以下の4つの引数を取る関数で書くことになります。
*nums 整数の配列
numsSize 整数の配列の要素の個数
target 合計値
*returnSize 関数が返す要素の個数
main関数の中も少し変更しました。
入力する整数値の個数を最初に入力させていましたが、これを省いていきなり
整数を入力することにしました。
このため、getsで1行の文字列としてデータを取得し、これをstrtok関数でトークンに分けて
個々の整数値を得る形にしました。
ただし、nums[10]としており、入力できる整数値の個数は10個までです。
strtok
文字列を区切り文字で分離する関数ですが、かなりクセの強い関数です。
#include <string.>
char* strtok(char* str1, const char* str2);
第一引数のstr1に分離したい文字列のアドレス（ポインタ）を指定します。
第二引数には、区切り文字列のアドレス（ポインタ）を指定します。
実行後、文字列の分離が成功した場合、分離された文字列へのアドレス（ポインタ）が返り値として
返されます。
文字列が分離できない場合はNULLが返されます。
同じ文字列に対して2回目の分離を行う場合は、第一引数str1にNULLを指定します。
atoi
数字の文字列を整数型に変換するのにatoiという関数を使います。
<TwoSumA.c>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* twoSum(int*, int, int, int*);
int main() {
int i,nums[10],target, returnSize, *result ;
char s[30], *token;
gets(s);
token=strtok(s," ");
i=0;
while (token !=NULL) {
nums[i]=atoi(token);
/* 続けて文字列の分離をするときはNULLを指定する */
token=strtok(NULL," ");
i++;
}
scanf("%d",&target);
result = twoSum(nums, i+1, target, &returnSize);
if (returnSize == 2) {
printf("Indices: %d, %d\n", result[0], result[1]);
} else {
printf("No solution found\n");
}
free(result); // 動的に確保したメモリを解放
return 0;
}
int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
int i,j;
for ( i = 0; i < numsSize; i++) {
for ( j = i + 1; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
int* result = (int*)malloc(2 * sizeof(int)); // 結果用の配列を動的に確保
result[0] = i;
result[1] = j;
*returnSize = 2; // 結果のサイズを returnSize にセット
return result;
}
}
}
*returnSize = 0; // 該当するペアが見つからなかった場合
return NULL;
}
（１） TwoSum2.1.cをC++にしてみる
TwoSum2.1.cをC++で書き換えてみました。
Cでは関数にしていたtwoSumをclassにしてみました。
twoSumクラスにsolveという関数を実装しています。関数solveの中のコードは
twosum2.1.cと同じです。
<twosum2.3.cpp.>
#include <stdio.h>
#include <stdlib.h>
class twoSum {
public:
int* solve(int numsize, int * num, int target);
};
int* twoSum::solve(int numsize, int * num, int target){
int i,j,*ret;
ret=(int*)malloc(2*(sizeof(int)));
ret[0]=-1; ret[1]=-1;
for (i = 0; i < numsize; i++) {
for (j = i+1; j < numsize; j++) {
/* since we start checking from index i+1, we don't
need to do i != j check inside the if condition
*/
if (num[i] + num[j] == target) {
ret[0]=i;ret[1]=j;
return ret;
}
}
}
return ret;
}
int main(void)
{
twoSum ts;
int n[20],i,nsize,t,*ret;
printf("number of input data:");
scanf("%d",&nsize);
printf("data:");
for (i=0;i<nsize;i++)
{scanf("%d",&n[i]);}
printf("target:");
scanf("%d",&t);
ret=ts.solve(nsize,n,t);
if (ret !=NULL) {
if (ret[0] == -1) {printf("No pair number\n");}
else {printf("result:%d, %d because %d + %d", ret[0], ret[1],n[ret[0]],n[ret[1]]);}
free(ret);
}
return 0;
}
（２） vector配列を使う
これまでのｐログラムは入力する整数値の上限が決まっていましたが、vectorで動的配列を使うことにより、
その制限をなくしました。
vectorで動的配列を使う時は
std::vector<型> オブジェクト名;
のように宣言します。
using namespace std;
としておけばstd:: は不要です。
vectorで宣言されたオブジェクト（変数）の要素数は、vectorクラスのメンバ関数size()を使います。
push_back() で配列の末尾にデータを追加し、pop_back()で末尾のデータを削除します。
配列の既存の要素へのアクセスは普通の配列と同じです。
twoSumクラスのsolve関数でretrunする変数retは、 vector<int> ret; として動的配列として宣言しているので、
関数solveも vector<int. solve() と宣言しておきます。
mainのnum,retもvectorで動的配列として宣言しています。
vectorで動的配列として宣言した場合、std::vectorクラスの内部でメモリを管理しているので、自分でmallocで領域確保
したりfree()で開放したりする必要はなくなります。
twoSum3.cpp>
#include <stdio.h>
#include <vector>
using namespace std;
class twoSum {
public:
vector<int> solve(vector<int>& num, int target);
};
vector<int> twoSum:: solve(vector<int>& num, int target){
vector<int> ret;
int n = num.size();
printf("solve\n");
ret.push_back(-1); ret.push_back(-1);
/* printf("%d, %d, %d\n",num[0],num[1],num[2]); */
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
/* since we start checking from index i+1, we don't
need to do i != j check inside the if condition
*/
if (num[i] + num[j] == target) {
ret[0]=i;ret[1]=j;
return ret;
}
}
}
return ret;
}
int main(void)
{
twoSum ts;
vector<int> num,ret;
int n,i,nsize,t;
printf("number of input data:");
scanf("%d",&nsize);
printf("data:");
for (i=0;i<nsize;i++)
{scanf("%d",&n);
num.push_back(n);}
printf("target:");
scanf("%d",&t);
ret=ts.solve(num,t);
if (ret[0] == -1) printf("No pair number\n");
else printf("result:%d, %d because %d + %d", ret[0], ret[1],num[ret[0]],num[ret[1]]);
return 0;
}
実行例（Borland C++55でコンパイル）
