算法题打卡力扣第167题：两数之和——输入有序数组（mid）

题目描述

提示：

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

解法一：暴力解

两个for循环
代码

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int n = numbers.size();int index1,index2;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(numbers[i]+numbers[j]==target){index1= i+1;index2 = j+1;break;}   }}return {index1,index2};}
};

执行如下：
超出时间限制了

复杂度分析：
时间复杂度分析：O(n^2),对于这道题来说太慢了，没有利用到数组的有序性
空间复杂度分析：O（1）

解法二:双指针法

算法思想：

因为数组是有序的，我们可以使用两个指针，一个从头开始，一个从尾开始，相向而行。

思路详解：
初始化两个指针：left 指向数组开头（索引 0），right 指向数组末尾（索引 n-1）。
进入循环，条件是 left < right。
计算两个指针指向的数字之和 sum = numbers[left] + numbers[right]。
进行判断：
如果 sum == target：太棒了，我们找到了答案！直接 return {left + 1, right + 1}。
如果 sum < target：说明当前的和太小了。为了让和变大，我们需要一个更大的数。由于数组是升序的，我们应该将左指针 left向右移动一位 (left++)，去尝试一个更大的数。
如果 sum > target：说明当前的和太大了。为了让和变小，我们需要一个更小的数。我们应该将右指针 right向左移动一位 (right–)，去尝试一个更小的数。
由于题目保证有解，这个循环一定会在 left 与 right 相遇前找到答案。
代码

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int n = numbers.size();int left = 0,right=n-1;int index1,index2,sum=0;while(left<right){sum = numbers[left]+numbers[right];if(sum==target){index1=left+1;index2=right+1;break;}else if(sum>target){right--;}else{left++;}}return {index1,index2};}
};

执行结果

复杂度分析：
时间复杂度分析：O(n)
空间复杂度分析：O（1）