西宁网站建设哪家公司好,thinkphp做的上线网站,企业网站内容如何更新,南宁做网站 的给你一个下标从 1 开始的整数数组 numbers #xff0c;该数组已按 非递减顺序排列 #xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] #xff0c;则 1 index1 index2 numbers…给你一个下标从 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] 。
思路一双指针
c解法
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();vectorint res;int left 0,right n-1;while(leftright){if(numbers[left]numbers[right]target)right--;if(numbers[left]numbers[right]target)left;if(numbers[left]numbers[right]target){res.push_back(left1);res.push_back(right1);return res;}}return res;}
};
分析
本题要返回两数之和等于目标数的两个数因为原数组已经按照非递减的顺序排列可以利用双指针来找到两个数当左指针和右指针两个数大于目标数则右指针向左移反之则左指针向右移直到找到符合的两个数返回时间复杂度为O(n)
总结
本题考察双指针的应用利用两边之和是否大于目标数来进行查找满足题目要求的常数级额外空间的要求
