草庐IT

【双指针思维模式】：理解双指针算法的思维模式和设计思路

吴NDIR 2023-04-13 原文

博客昵称：吴NDIR
个人座右铭：得之淡然，失之坦然
作者简介：喜欢轻音乐、象棋，爱好算法、刷题
其他推荐内容
计算机导论速记思维导图
五种排序算法
二分查找入门讲解

今天让我们聊一下双指针吧！在一些算法中，使用双指针可以使时间复杂度得到很大的优化。

索引

概念

  • 双指针是指在某些问题中，我们需要在数组、字符串或其他数据结构中使用两个指针（通常指向不同位置），以便我们可以同时操作它们，并解决特定的问题。
  1. 问题：假设我们要在已排序的数组中查找两个数，使它们的和为一个特定的目标值（target）。
小吴去市场买鱼，它应该怎么从已有的稽币中拿出两张付给老板？
  • 从问题中我们可以知道给定的数组[2,4,5,8,20]以及target=13,可能比较直接的思路就是暴力破解
  1. 暴力破解的思路是遍历每对数，直到找到两个数等于目标和或者已经遍历完所有可能的数对。
  2. 具体地，可以使用两个嵌套循环，外层循环从数组的第一个元素开始遍历，内层循环从外层循环中的元素的下一个元素开始遍历，直到遍历完整个数组，这样就可以找出两个元素之和等于目标和的情况。
  3. 在代码实现中，当找到两个元素之和等于目标和的情况时，直接输出这两个元素并返回，否则说明在数组中找不到所需的两个数，则输出“找不到”。
但是，这种暴力解法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，因为需要嵌套两层循环，因此一旦输入的数组很大，算法所需要的时间也会随之增大。因此在处理大规模问题时，这种暴力解法通常不是一个好的选择.
  • 更好的选择是使用优化算法，例如双指针。
  1. 首先将两个指针指向数组的两端，即一个指针指向数组的第一个元素，另一个指针指向数组的最后一个元素。
  2. 接着，根据两个指针所指向元素的和与目标和的大小关系来移动指针。如果两个元素的和小于目标和，则将指向较小元素的指针右移，寻求更大的元素。如果两个元素的和大于目标和，则将指向较大元素的指针左移，寻求更小的元素。如果两个元素的和等于目标和，则直接返回这两个元素。
此双指针算法的时间复杂度为 O(n)，因为将两个指针移动到最中间的时候问题必定会被解决。和无序数组的暴力解法相比，使用双指针算法可以有效地提高查找效率，适用于较大的数组，并且避免了需要嵌套的循环，提高程序的运算效率。
对比：我们可以看到，当数组元素较多时，双指针的优势就显露出来了。

代码实现

void find(int arr[], int n, int targetSum) {
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == targetSum) {
            printf("这两个数分别是 %d 和 %d", arr[left], arr[right]);
            return;
        } else if (sum < targetSum) {
            left++;
        } else {
            right--;
        }
    }
    printf("不存在两个数之和等于目标值");
}
  • 示例
int main() {
    int arr[] = {2, 3, 5, 7, 11};//例子
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;//目标值
    find(arr, n, target);
    return 0;
}
  • 结果

引例

  • 题目描述：给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

示例1

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例2

输入: nums = [0]
输出: [0]

讲解

  • 这道题目的思路是使用双指针来遍历整个数组，其中一个指针left表示当前非零元素应该被放置的位置，另一个指针right则用来遍历整个数组。当right指向一个非零元素时，就将它与left指向的位置的元素进行交换，然后left向后移动一位，以便下一个非零元素可以被放置在正确的位置。当right遍历完整个数组时，left的位置右边应全为0。以下是步骤：
  1. 用两个指针left和right初始化为0；
  2. 遍历数组，当nums[right]不为0时，就将nums[left]与nums[right]交换，并将left向后移动一位；
  3. 遍历完整个数组后，数组中所有的0都已经移动到了末尾，完成。

示例代码

//交换对应元素
void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}
void move(int *nums, int numsSize) {
    int left = 0, right = 0;
    while (right < numsSize) {
    //当nums[right]不为0时
        if (nums[right]) {
            swap(nums + left, nums + right);
            left++;
        }
        right++;
    }
}
双指针spanclasstoken算法数据结构排序算法c语言经验分享

有关【双指针思维模式】：理解双指针算法的思维模式和设计思路的更多相关文章

  1. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  4. ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2

    我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它​​不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数

  5. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  6. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  7. LC滤波器设计学习笔记（一）滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称

  8. CAN协议的学习与理解 - 2

    最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总

  9. 计算机毕业设计ssm+vue基本微信小程序的小学生兴趣延时班预约小程序 - 2

    项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明：前端使用微信微信小程序开发工具：后端使用ssm：VU

  10. TimeSformer：抛弃CNN的Transformer视频理解框架 - 2

    Transformers开始在视频识别领域的“猪突猛进”，各种改进和魔改层出不穷。由此作者将开启VideoTransformer系列的讲解，本篇主要介绍了FBAI团队的TimeSformer，这也是第一篇使用纯Transformer结构在视频识别上的文章。如果觉得有用，就请点赞、收藏、关注！paper:https://arxiv.org/abs/2102.05095code(offical):https://github.com/facebookresearch/TimeSformeraccept:ICML2021author:FacebookAI一、前言Transformers(VIT)在图

随机推荐