167. 两数之和 II - 输入有序数组【 力扣(LeetCode) 】

一、标题形貌

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减序次分列  ，请你从数组中找出满意相加之和便是目的数 target 的两个数。假如设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的情势返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用雷同的元素。
你所计划的办理方案必须只使用常量级的额外空间。
二、测试用例

示例 1：

1. 输入：numbers = [2,7,11,15], target = 9
2. 输出：[1,2]
3. 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

复制代码

示例 2：

1. 输入：numbers = [2,3,4], target = 6
2. 输出：[1,3]
3. 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

复制代码

示例 3：

1. 输入：numbers = [-1,0], target = -1
2. 输出：[1,2]
3. 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

复制代码

提示：

1. 2 <= numbers.length <= 3 * 104
2. -1000 <= numbers[i] <= 1000
3. numbers 按 非递减顺序 排列
4. -1000 <= target <= 1000
5. 仅存在一个有效答案

复制代码

三、解题思绪

• 根本思绪：
    双指针，头指针加尾指针遍历，相加便是目的值则返回下标。
  
• 具体思绪：
  
  
  
  • 预处置惩罚：界说头指针 i 和 尾指针 j ，用于遍历，初始化为 0 和 n-1 。序列按非递减序次分列，以是指针 i 所指元素最小，j 最大。
    
  • 遍历：判定两指针所指元素之和是否便是目的值，假如小于目的值，则增大两元素之和，而尾指针已经是最大，以是只能增大头指针，即 i++ ；假如大于目的值，则减小两元素之和，即 j-- ；假如相称，则找到答案，则返回两元素下标。【使用只能增长和只能淘汰 来淘汰搜刮空间，将 O(n2)\Omicron(n^2)O(n2) 低沉至 O(n)\Omicron(n)O(n)
    
  
  

四、参考代码

时间复杂度：O(n)\Omicron(n)O(n)
空间复杂度：O(1)\Omicron(1)O(1)

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& numbers, int target) {
4.         int n=numbers.size();
5.         int i=0,j=n-1;
6.         vector<int> ans;
8.         while(i<j){
9.             if(numbers[i]+numbers[j]<target)
10.                 i++;
11.             else if(numbers[i]+numbers[j]>target)
12.                 j--;
13.             else{
14.                 ans.push_back(i+1);
15.                 ans.push_back(j+1);
16.                 break;
17.             }
18.         }
19.         
20.         return ans;
21.     }
22. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金