??博客主頁：程序員葵安

??感謝大家點贊????收藏?評論???

一、兩數之和 Ⅱ（167）

1.1 題目介紹

給你一個下標從 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
• 僅存在一個有效答案

1.2 題目詳解

暴力做法：for循環枚舉第一個數，內嵌一個for循環枚舉第二個數，時間復雜度為O()

優化思路：數組已排序，但暴力并未利用數組已排序的性質。已排序的數組下，如果當前剩下的最小數與最大數之和大于目標值，則中間的數與最大數之和大于目標值，則最大數可被排除。如果將當前剩下的最小數與所選最大數之和小于目標值，則中間的數與最小數之和小于目標值，則最小數可排除。時間復雜度為O(n)

代碼實現：

class Solution {public int[] twoSum(int[] numbers, int target) {int left = 0;int right = numbers.length - 1;while (true) {int s = numbers[left] + numbers[right];if (s == target) {return new int[]{left + 1, right + 1};}if (s > target) { right--;} else {left++;}}}
}

二、 三數之和（15）

2.1 題目介紹

給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 <