4

LeetCode 第 167 号问题:两数之和 II – 输入有序数组

 2 years ago
source link: https://www.cxyxiaowu.com/6908.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 167 号问题:两数之和 II – 输入有序数组-程序员小吴
当前位置:程序员小吴 > LeetCodeAnimation > LeetCode 第 167 号问题:两数之和 II – 输入有序数组

本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。

个人网站:https://www.cxyxiaowu.com

题目来源于 LeetCode 上第 167 号问题:两数之和 II – 输入有序数组。题目难度为 Easy,目前通过率为 48.2% 。

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

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

初始化左指针 left 指向数组起始,初始化右指针 right 指向数组结尾。

根据已排序这个特性,

  • (1)如果 numbers[left] 与 numbers[right] 的和 tmp 小于 target ,说明应该增加 tmp ,因此 left 右移指向一个较大的值。
  • (2)如果 tmp大于 target ,说明应该减小 tmp ,因此 right 左移指向一个较小的值。
  • (3)tmp 等于 target ,则找到,返回 left + 1 和 right + 1。(注意以 1 为起始下标)
59rnm.gif
// 对撞指针
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while(l < r){
            if(numbers[l] + numbers[r] == target){
                int res[2] = {l+1, r+1};
                return vector<int>(res, res+2);
            }
            else if(numbers[l] + numbers[r] < target)
                l ++;
            else // numbers[l] + numbers[r] > target
                r --;
        }
    }

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK