LeetCode做題筆記第167題：兩數之和 II - 輸入有序數組

題目描述

給定一個已按照 升序排列 的整數數組 numbers ，請你從數組中找出兩個數滿足相加之和等于目标數 target 。

函數應該以長度為 2 的整數數組的形式傳回這兩個數的下标值。numbers 的下标 從 1 開始計數 ，是以答案數組應當滿足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假設每個輸入隻對應唯一的答案，而且你不可以重複使用相同的元素。

示例1

輸入：numbers = [2,7,11,15], target = 9

輸出：[1,2]

解釋：2 與 7 之和等于目标數 9 。是以 index1 = 1, index2 = 2 。

執行個體2

輸入：numbers = [2,3,4], target = 6

輸出：[1,3]

解題思路

一開始的思路就是雙層for循環，最外層i從0開始，裡層的j從i+1開始，就拿示例1舉例子，依次比較2+7,2+11,2+15,7+11,7+15,11+15,正常測試用例少的話，這樣寫是可以的，但是效率不是太高，而在LeetCode裡逾時了。

是以稍微轉換一下思路，關鍵字，

雙指針

，采用while循環，定義兩個變量left和right，分别從最左邊和最右邊進行比較，若之和大于target，則需要把right-1，之和小于target則讓left+1，就可以了。接下來上代碼。

完整代碼

static void Main(string[] args)
        {
            int[] numbers = new int[] { 2,3,4 };
            int target = 6;
            var result = TwoSum(numbers, target);
            foreach (var item in result)
            {
                Console.Write(item+",");
            }
            Console.ReadKey();
        }
 public static int[] TwoSum(int[] numbers, int target)
        {
            var result = new int[2];
            int left = 0;
            int right = numbers.Length - 1;
            while (left<right)
            {
                if (numbers[left] + numbers[right] == target)
                {
                    result[0] = ++left;
                    result[1] = ++right;
                    break;
                }
                else if(numbers[left] + numbers[right] < target)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
            return result;
        }
           

study hard and make progress every day.