首页 > 其他分享 >两数之和(双指针法)

两数之和(双指针法)

时间:2024-11-02 19:51:54浏览次数:3  
标签:right target numbers 数组 指针 两数 left

 

给你一个下标从 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] 。

提示:

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

 

 双指针法(Two-Pointer Technique):

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];

            if (sum == target) 
                break;
            if (sum < target)
                left++;
            else
                right--;
        }
        
        return {left + 1, right + 1};
    }
};

在这个问题中,由于数组已按非递减顺序排列,双指针法利用了数组的有序性,让我们可以在一个线性时间复杂度内找到满足条件的两个数的下标。

left 指针从数组的开头(最小值)开始,right 指针从数组的末尾(最大值)开始。通过不断调整这两个指针来逼近目标值 target

在每一步中,计算 numbers[left] + numbers[right] 的和。

  • 如果和等于 target:我们已经找到解 [left + 1, right + 1](题目要求下标从 1 开始)。
  • 如果和小于 target:说明当前组合的和不够大。因为数组是有序的,增加 left 指针使其指向更大的数有助于增大和,从而更接近 target
  • 如果和大于 target:说明当前组合的和太大了。减小 right 指针可以使其指向一个较小的数,从而减小和,更接近 target

 

时间和空间效率

  • 双指针法通常在 O(n) 时间内完成操作,因为每个指针只朝一个方向单调地移动,且不会回头或在同一个位置重复计算
  • 空间复杂度是 O(1),因为只使用了常数额外空间,不需要额外的数据结构。

 

numbers = {2, 7, 11, 15}target = 9 为例:

  1. 初始化:left = 0(指向 2),right = 3(指向 15)

    • sum = numbers[left] + numbers[right] = 2 + 15 = 17 > target,因为和太大,右指针左移。
  2. 更新指针:left = 0right = 2(指向 11)

    • sum = 2 + 11 = 13 > target,和仍然太大,右指针继续左移。
  3. 更新指针:left = 0right = 1(指向 7)

    • sum = 2 + 7 = 9 == target,找到符合条件的下标 [1, 2](下标从 1 开始)。

标签:right,target,numbers,数组,指针,两数,left
From: https://blog.csdn.net/Ct314/article/details/143308380

相关文章

  • C++ 手撕--共享式智能指针(shared_ptr)的简单实现
    C++手撕--共享式智能指针(shared_ptr)的简单实现共享式智能指针(shared_ptr):#include<iostream>#include<mutex>usingnamespacestd;template<typenameT>classShared_ptr{private:T*ptr;int*ref_count;std::mutex*mtx;voidrelease(){......
  • java平方根计算 C语言指针变量
    1.publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);System.out.println("请输入你的数:");intnum=sc.nextInt();for(inti=1;i<=num;i++){if(i*i==num){System.out.println(i+"就是......
  • 【算法】【优选算法】双指针(上)
    目录一、双指针简介1.1对撞指针(左右指针)1.2快慢指针二、283.移动零三、1089.复写零3.1双指针解题3.2暴力解法四、202.快乐数4.1快慢指针4.2暴力解法五、11.盛最多⽔的容器5.1左右指针5.2暴力解法一、双指针简介常⻅的双指针有两种形式,⼀种是对撞指针,⼀......
  • 深入学习指针!指针史上最全解析!!(1)
    文章目录1.内存和地址1.1内存1.2究竟该如何理解编址2.指针变量和地址2.1取地址操作符(&)2.2指针变量和解引用操作符(*)2.2.1指针变量2.2.2如何拆解指针类型2.2.3解引用操作符2.3指针变量的大小3.指针变量类型的意义3.1指针的解引用3.2指针+-整数3.3void*指针4.指针运......
  • 双指针习题篇(下)
    双指针习题篇(下)文章目录双指针习题篇(下)1.有效三角形的个数题目描述:解法一:暴力枚举(超时)算法思路:代码实现:解法二:利用单调性,使用双指针算法来解决问题算法思路:算法流程:代码实现:2.和为s的两个数字题目描述:解法一:暴力枚举O(N^2^)算法思路:算法流程:代码实现:解法二......
  • 【无标题】Acwing1238_日志统计(双指针)
    原题链接 :1238.日志统计-AcWing题库https://www.acwing.com/problem/content/1240/题目要求:/***小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有N行。*其中每一行的格式是:tsid表示在ts时刻编号id的帖子收到一个”赞”。*现在小明......
  • 深入理解指针(1)
    1:内存和地址1:内存我们知道计算机上面的CPU在处理数据时,需要的数据是在内存中读取的,处理后的数据也会放回内存中,那我们买电脑时,电脑内存是8GB/16GB/32GB等,那这些内存空间如何高效管理呢?其实也是内存划分为一个个的内存单元,每个内存的大小取1个字节。一个bit(比特)位可以储存一......
  • 单链表题+数组题(快慢指针和左右指针)
    @目录说明:本文章用于“单链表题+数组题”“链表”知识一、案例说明(使用快慢指针)问题1.1判断链表是否有环问题1.2:已知链表有环,请返回这个环的起点位置问题1.3:寻找无环单链表的中点,要求:如果偶数个数以左面一个节点为中点问题1.4:寻找无环单链表的中点,要求:如果偶数个数以右面一个节......
  • C语言中指针和数组的相互关系
    在C语言中,指针和数组有着紧密的相互关系。数组是数据的集合,而指针则是一个包含内存地址的变量。指针可以用来访问数组的元素,便于高效的内存访问和操作。更具体来说,数组名本身就是一个指向首元素的指针、通过指针运算,我们可以遍历数组的每个元素、数组和指针的索引操作是等价的、......
  • 智能指针使用
    普通指针的不足new和new[]的内存需要用delete和deletel]释放。程序员的主观失误,忘了或漏了释放。程序员也不确定何时释放。普通指针的释放类内的指针,在析构函数中释放。C++内置数据类型,如何释放?new出来的类,本身如何释放?C++11新增三个智能指针类型unique_pt......