167. 兩數之和 II - 輸入有序數組

給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等于目標數。

函數應該返回這兩個下標值 index1和 index2，其中 index1必須小于 index2。

說明:

• 返回的下標值（index1和 index2）不是從零開始的。
• 你可以假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。

示例1 ：

輸入: numbers = [2, 7, 11, 15], target = 9 輸出: [1,2] 解釋: 2 與 7 之和等于目標數 9 。因此 index1 = 1, index2 = 2 。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/path-sum 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

題解：

本題首先想到就應該是雙指針法，思路也很簡單，就是一個指針指向開頭，另一個指針指向結尾，然后判斷指針所指向的兩數之和是否等于target，如果相等就返回相應的index；如果不等判斷兩數之和和target的大小，如果和大于target，則需要index2向左移動以此來縮小和，如果和小于target，則需要index1向右移動以此來增大和。

具體代碼如下：

class Solution {public int searchInsert(int[] nums, int target) {if (nums.length == 0) return -1;int left = 0;//這里用right = nums.length，下面的while循環條件就用left < right//這里如果是right = nums.length - 1，下面的循環條件就是left <= right//這是因為使用right = nums.length循環判等的話會出現越界int right = nums.length;while (left < right) {int mid = left + (right - left) / 2; //防止left和right太大導致相加除二溢出if (nums[mid] == target) { //如果target就是nums[mid]的值的話就直接返回return mid;}if (target > nums[mid]) { //如果target比nums[mid]大，我們向右子區間收縮，所以這里需要left = mid + 1left = mid + 1;}if (target < nums[mid]) {//因為我們上面的right = nums.length，并且循環條件為left < right//所以這里不能使用right = mid - 1，具體的大家可以debug觀察結果right = mid;}}return left;} }

官方提示中還提到了二分查找，由于二分查找不能同時進行兩個數的查找，我們最先能想到的就是固定一個數，然后去剩下的元素中找，看能不能找到一個值和target - numbers[i]的值相等，如果能，則返回兩者索引，如果不能，則返回-1。

具體代碼如下：

public class Solution {public int[] twoSum(int[] numbers, int target) {int right = numbers.length - 1;//固定一個值，在剩下的元素中找一個數是否等于target - numbers[i]的值for (int i = 0; i < numbers.length; i++) {if (numbers[i] + numbers[right] == target) {return new int[]{i + 1, right + 1};}int index2 = binarySearch(numbers, i + 1, right, target - numbers[i]);if (index2 != -1) {return new int[]{i + 1, index2 + 1};}}return new int[]{-1, -1};}//手寫binarySearch()方法，當然也可以直接調用Arrays.binarySearch()方法public int binarySearch(int[] nums, int fromIndex, int toIndex, int target) {int left = fromIndex;int right = toIndex - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target)return mid;else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;}}return -1;} }

總結

以上是生活随笔為你收集整理的leetcode 两数相加c++_167. 两数之和 II - 输入有序数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。