[167] Two Sum II - Input Array Is Sorted

在那邊想說要用binary search !!!

笑我自己傻ToT

一開始寫了暴力解，兩個回圈不意外的超過時間XD

掙扎了一下binary search 然後才發現用two pointer 簡直秒解 lol

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

#if 1

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){

int i=0,j=numbersSize-1;

int* ret=calloc(2,sizeof(int));

*returnSize =2;

while(i<j)

{

int sum = numbers[i]+numbers[j];

if (sum> target)

j--;

else if (sum < target)

i++;

else

break;

}

ret[0]=i+1;

ret[1]=j+1;

return ret;

}

#else    // brute force

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){

int i,j;

int* ret=calloc(2,sizeof(int));

*returnSize =2;

for (i=0;i<numbersSize;i++)

{

for (j=i+1;j<numbersSize;j++)

if (numbers[i]+numbers[j]==target)

break;

if (j!=numbersSize)

break;

}

ret[0]=i+1;

ret[1]=j+1;

return ret;

}

#endif