題目
給你一個下標從 1 開始的整數(shù)數(shù)組numbers喳魏，該數(shù)組已按非遞減順序排列客们，請你從數(shù)組中找出滿足相加之和等于目標數(shù) target 的兩個數(shù)。如果設(shè)這兩個數(shù)分別是 numbers[index1] 和 numbers[index2] 彰触，則 1 <= index1 < index2 <= numbers.length 都许。
以長度為 2 的整數(shù)數(shù)組 的形式返回這兩個整數(shù)的下標
和
。
你可以假設(shè)每個輸入 只對應(yīng)唯一的答案 押桃，而且你 不可以 重復(fù)使用相同的元素葵萎。
你所設(shè)計的解決方案必須只使用常量級的額外空間。
示例1
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標數(shù) 9 唱凯。因此 index1 = 1, index2 = 2 羡忘。返回 [1, 2] 。
示例2
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標數(shù) -1 磕昼。因此 index1 = 1, index2 = 2 卷雕。返回 [1, 2] 。
思路
使用雙指針票从，左指針指向數(shù)組頭部漫雕，右指針指向數(shù)組尾部滨嘱，壓縮搜索空間進行查找。
代碼實現(xiàn)
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
int left = 0;
int right = numbersSize - 1;
int * result = (int *)malloc(sizeof(int) * 2);
*returnSize = 2;
while(left < right){
int temp = numbers[left] + numbers[right];
if(temp < target){
left++;
}else if(temp > target){
right--;
}else{
result[0] = left+1;
result[1] = right+1;
return result;
}
}
result[0] = -1;
result[1] = -1;
return result;
}
