【leetcode】21. 序列-和为s的两个数字
题目
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
难易程度:easy
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
示例 2:
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
限制:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
分析
本题和《【leetcode】5. 数组-两数之和》列数,不通的地方是本题给出的数组是递增有序的。因此可以利用这条件来进行优化求解。
基本方法是利用双指针法,遍历求和。设有两个指针(下标)int left = 0, right = nums.size() - 1;
循环求解um = nums[left] + nums[right];
- 如果
sum == target
则返回对应下标元素 - 如果
sum < target
则left++
- 否则
rigth--
时间复杂度:O(N)
空间复杂度:O(1)
代码
1 | class Solution { |