《信息学C++知识讲解》:双指针的使用总结(二)

《信息学C++知识讲解》:双指针的使用总结(二)

双指针是一种解决问题的技巧或者思维方式,指在访问一个序列中的数据时使用两个指针进行扫描,两个指针可以是同向的,也可以是反向的;我们的关注点可以是这两个指针指向的两个元素本身,也可以是两个指针中间的区域。

左右指针

01、左右指针的概念
左右指针是初始将两个指针分别放在头和尾的位置,然后相向开始移动,直到两个指针相遇;左右指针一般用在有序数组中,可以批量的排除不符合要求的元素,将两重循环O(n2)的时间复杂度转化为一重循环O(n+m)的线性复杂度。

02、应用示例-二分查找

二分查找就是利用有序的特点,一次可以排除一半数据。

//nums中查找等于target的元素的下标int searchInsert(vector<int>& nums, int target) {      int left = 0;      int right = nums.size()-1;      while(left <= right)      {          int mid = left + (right-left)/2;          if( nums[mid] > target )//mid处的元素值比target大,则区间[mid,right]中的元素都比target大          {              right = mid-1;//缩小右边界,排除一半数据          }          else  if( nums[mid] < target )//mid处的元素值比target小,则区间[left,mid]中的元素都比target小          {              left = mid +1;//扩大左边界,排除一半数据          }          else          {              resault = mid;//找到等于target 的元素了          }      }      return -1; }

03、应用示例-两数之和Ⅱ-输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。说明: 返回的下标值(index1 和 index2)不是从零开始的。你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

力扣(LeetCode)第167题

常规暴力解法也是使用双指针,先固定一个指针 left,然后另一个指针 right 开始遍历,若没有找到,则移动 left ,然后再次用 right 进行遍历。

利用数组已经有序的特点,可以参考二分查找的思想,批量的进行排除数据。开始将 left 、right 分别放在数组的两端,比较 nums[left] + nums[right]:

  • 若 nums[left] + nums[right] > target ,因为nums[left] 已经是最小值,则  right 和 [left,right-1] 中的元素组合都可以排除;需要缩小right
  • 若 nums[left] + nums[right] < target ,因为nums[right] 已经是最大值,则 left 和 [left+1,right] 中的元素的组合都可以排除;需要增大left
class Solution {public:    vector<int> twoSum(vector<int>& numbers, int target) {        int left = 0, right = numbers.size() - 1;//初始化left和right指针        while (left < right)         {            int sum = numbers[left] + numbers[right];            if (sum == target)                return {left + 1, right + 1};            else if (sum < target)//比target小,则需要增大较小的数                left++;            else//比target大,则需要缩小较大的数                right--;        }        return {-1, -1};    }};
叮当学习力:数理逻辑思维课
点图或扫码领0元课
叮当学习力-逻辑思维
更多课程

 

微信扫码领取0元编程课


核桃编程-弹窗图

This will close in 180 seconds

少儿编程0元课

 
少儿编程0元课  

少儿0元课导航

 
少儿0元课导航  

少儿逻辑0元课

 
少儿逻辑0元课  

公众号

关注公众号

x
少儿编程学习网
专注青少年编程学习、课程推荐、科技特长生规划
2023-01-27 06:39:43
您好,有任何疑问请与我们联系!
您的工单我们已经收到,我们将会尽快跟您联系!
[官方群:675726029]
[Mars老师:Qbit-School]
[Mars老师]
17732463686
取消

选择聊天工具: