給你一個下標從 1 開始的整數數組 numbers ，該數組已按 非遞減順序排列  ，請你從數組中找出滿足相加之和等于目標數 target 的兩個數。如果設這兩個數分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。以長度為 2 的整數數組 [index1, index2] 的形式返回這兩個整數的下標 index1 和 index2。你可以假設每個輸入 只對應唯一的答案 ，而且你 不可以 重復使用相同的元素。你所設計的解決方案必須只使用常量級的額外空間。示例 1：輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標數 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等于目標數 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標數 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非遞減順序 排列
-1000 <= target <= 1000
僅存在一個有效答案

167. 兩數之和 II - 輸入有序數組 - 力扣（LeetCode）

算法設計

? ? ? ? 拿到這道題，想到了很多方法？二分法？哈希表？但是他們都有自己的弊端，二分法必須套在二層循環里，哈希表必須使用桶式結構來保存哈希標簽重合的Index，且代碼邏輯比較復雜。

? ? ? ? 想要以最快速度解決這道題，真正的入手點在數學。首先需要意識到一個點，我們是能通過不斷求取局部最優解來獲得全局最優解的，為什么這么說？

? ? ? ? 求解規則：

? ? ? ? 1. 定義頭指針尾指針，并分別初始化在表頭表尾。

? ? ? ? 2. 如果頭尾指針指向元素和等于target，則返回標簽

? ? ? ? 3. 如果頭尾指針指向元素和大于target，尾指針--；

? ? ? ? 4. 如果頭尾指針指向元素和小于target，尾指針++；

? ? ? ? 5. 跳到2直到head和tail重合或tail<head;

? ? ? ? 為什么能如此自信的通過一步步貪心求得最終解？難道這個過程中不會遺漏掉最終解嗎？

? ? ? ? 我們正常推理不太好思考，不如用反證法：

? ? ? ? 假設上述求解規則中，兩個最終標簽解被稱為小解和大解。會出現head大于小解或tail小于大解的情況：

? ? ? ? 1. head大于小解，tail大于等于大解 =》則必然有一刻head等于小解，tail大于大解 =》此時頭尾指向和必然大于target =》則tail左移即可得到結果，head沒有機會右移 =》不存在head大于小解tail大于等于大解，與題設矛盾

? ? ? ? 2. head小于等于小解，tail小于大解 =》某一刻有tail等于大解，head小于小解 =》頭尾指向和小于target =》此時head右移即可求解，tail沒有機會左移 =》不存在head小于等于小解，tail小于大解，與題設矛盾

? ? ? ? 命題得證

代碼實現

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {int head=0,tail=numbersSize-1;int * ret=(int*) malloc(sizeof(int)*2);while(head<tail){if(*(numbers+head)+*(numbers+tail)==target){ret[0]=head+1;ret[1]=tail+1;*(returnSize)=2;return ret;}if(*(numbers+head)+*(numbers+tail)>target){tail--;}if(*(numbers+head)+*(numbers+tail)<target)head++;}*(returnSize)=0;return ret;
}

????????

????????

????????