[ 題目描述 ]：

[ 思路 ]：

• 題目要求求數值numbers中的和為 target 的兩個數的下標
• 最簡單的思路就是暴力求解，兩兩挨個組合，但時間復雜度為O(n²)，不一定能通過
• 因為數組為非遞減，那我們可以使用雙指針，并從數組首尾出發
  • 如果 和 > target，則右指針向左移動，因為左邊的數小于右邊
  • 如果 和 < target，則左指針向右移動，因為右邊的數大于左邊
• 運行如下
  

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {int left=0,right=numbersSize-1;int* ans=(int*)malloc(sizeof(int)*2);*returnSize=2;while(left<right){if(numbers[left]+numbers[right]==target){ans[0]=left+1;ans[1]=right+1;break;}else if(numbers[left]+numbers[right]>target){right--;}else{left++;}   }return ans;
}

• 時間復雜度O(n)，空間復雜度O(1)

[ 官方題解 ]：

• 一、二分查找，在數組中找到兩個數，使得它們的和等于目標值，可以首先固定第一個數，然后尋找第二個數，第二個數等于目標值減去第一個數的差。利用數組的有序性質，可以通過二分查找的方法尋找第二個數。為了避免重復尋找，在尋找第二個數時，只在第一個數的右側尋找。

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {int* ret = (int*)malloc(sizeof(int) * 2);*returnSize = 2;for (int i = 0; i < numbersSize; ++i) {int low = i + 1, high = numbersSize - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (numbers[mid] == target - numbers[i]) {ret[0] = i + 1, ret[1] = mid + 1;return ret;} else if (numbers[mid] > target - numbers[i]) {high = mid - 1;} else {low = mid + 1;}}}ret[0] = -1, ret[1] = -1;return ret;
}

• 二、雙指針，如上