详解C语言中双指针算法的使用

目录
  • 前言
  • 一、最长不含重复字符的子字符串
    • 1.题目要求
    • 2.个人题解
  • 二、和为S的两个数字
    • 1.题目要求
    • 2.个人题解

前言

双指针算法

算法思想

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

今天带大家来学习算法中双指针的应用场景。

一、最长不含重复字符的子字符串

1.题目要求

2.个人题解

2.1 解题思路

利用双指针，定义一个指针i和一个指针j

让i开始走，固定住j，然后我们利用一个辅助数组来记录下每个字符出现的次数。

比如对于字符串“abcabcdd”，当i走到第二个a的时候，a出现了两次，这时候让j开始向前走，走到b。

这时候i和j之间的字符串是bca。没有重复的，i可以继续走，j继续固定。

i走到b的时候b出现两次。这时候要移动j直至没有字符出现次数超过两次。如此反复直到i走到字符串结尾。

2.2 代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int S[128];
        memset(S,0x00, sizeof(S));
        int ans = 0;
        for(int i=0,j=0;i<len;++i)
        {
            S[s.at(i)]++;
            while(S[s.at(i)]>1)
            {
                S[s.at(j)]--;
                j++;
            }
            ans=max(ans,i-j+1); //更新区间最大长度
        }
        return ans;
    }
};

2.3 代码解析

首先定义数组S[128]，利用memset函数来初始化该数组。

memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。

for循环里声明i，j 为0，先让字符串的第一个字符对应的整数作为数组S的下标，该位置元素值加一；

如果没有重复字符，ans递增；如果有重复字符今后进入while循环，随着j的递增，之前数组里为一的元素值都会减一，为2的元素值也会减一并变为一；

接着j固定，i继续增长，再有重复字符就会重复上述操作，最终通过max函数得到最大的无重复子字符串长度。

二、和为S的两个数字

1.题目要求

2.个人题解

2.1 解题思路

根据题目可知该数组是升序排列，那我们可以用两个指针：一个在左边界，一个在右边界。

如果数组下标对应的值相加比num小，那么就让左边指针递增，反之则右边指针递减。

如果左右指针相等，说明没有满足条件的数对，返回空数组。

如果存在该数对，利用push_back方法插入数组并返回即可

2.2 代码实现

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left,right;
        int i,j,k;
        vector<int> res;
        left=0;
        right=array.size()-1;
        //如果数组为空,返回空数组
        if(array.empty()){
            return res;
        }
        while(array[left]+array[right]!=sum && left!=right){
            if(array[left]+array[right]<sum){
                left+=1;
            }else if(array[left]+array[right]>sum){
                right-=1;
            }
        }
        //如果不存在该数对,返回空数组
        if(left==right){
            return res;
        }
        //如果存在
        res.push_back(array[left]);
        res.push_back(array[right]);
        return res;
    }
};

本题思路确定后代码比较好理解，就没有分析部分了。

这两道题都是双指针的解法：第一题相当于是相邻指针，第二题则是双端指针，各有特色。

到此这篇关于详解C语言中双指针算法的使用的文章就介绍到这了,更多相关C语言 双指针算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言双指针算法朋友过情人节我过算法

    C语言双指针算法朋友过情人节我过算法

    目录 双指针 对撞指针 快慢指针 真题实战 双指针 首先咱得知道何为双指针,听起来很上流,其实有手就行. 双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的. 换言之,双指针法充分使用了数组有序这一特征,当遇到有序数组时,应该优先想到双指针来解决问题,因两个指针的同时遍历会减少空间复杂度和时间复杂度从而在某些情况下能够简化运算 对撞指针 类似于相遇问题,对撞指针是指在有序数组中,将指向最左侧

  • C语言双指针多方法旋转数组解题LeetCode

    C语言双指针多方法旋转数组解题LeetCode

    目录 暴力思路 外加数组 格局抬高 环形替代 LeetCode题目如下: 首先这个中等难度我是没搞懂,后面才发现原来中等中在要求多方法上,那就来看看怎么搞定他吧. 暴力思路 首先我说一下我本人的思路,就是函数进行倒序操作,分三步: 1.整体倒序 :1234567-------7654321 2.前半部分倒序:7654321------- 5674321 3.后半部分倒序:5674321-------5671234 由于题目已经给出了我们 k 的值,我们直接暴力思路(注意是暴力思路非暴力求解),双

  • C语言基础双指针移除元素解法

    C语言基础双指针移除元素解法

    本题方法:双指针.知识比较基础,思路简单 题目: 我的题解: int removeElement(int* nums, int numsSize, int val) { int i=0,j=0; int cnt=0; //计数器,用来统计val的个数 while(j<numsSize) { if(nums[j]!=val) //1 { nums[i]=nums[j]; i++; j++; } else //2 { j++; cnt++; } } return numsSize-cnt; //3

  • 详解C语言中双指针算法的使用

    详解C语言中双指针算法的使用

    目录 前言 一.最长不含重复字符的子字符串 1.题目要求 2.个人题解 二.和为S的两个数字 1.题目要求 2.个人题解 前言 双指针算法 算法思想 双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的. 换言之,双指针法充分使用了数组有序这一特征,从而在某些情况下能够简化一些运算. 今天带大家来学习算法中双指针的应用场景. 一.最长不含重复字符的子字符串 1.题目要求 2.个人题解 2.1

  • 详解C语言中二分查找的运用技巧

    详解C语言中二分查找的运用技巧

    目录 基础的二分查 查找左侧边界 查找右侧边界 二分查找问题分析 实例1: 爱吃香蕉的珂珂 实例2:运送包裹 前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素.查找第一个和目标值相等的元素.查找最后一个和目标值相等的元素 三种情况. 这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 . 本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查

  • 详解Go语言中关于包导入必学的 8 个知识点

    1. 单行导入与多行导入 在 Go 语言中,一个包可包含多个 .go 文件(这些文件必须得在同一级文件夹中),只要这些 .go 文件的头部都使用 package 关键字声明了同一个包. 导入包主要可分为两种方式: 单行导入 import "fmt" import "sync" 多行导入 import( "fmt" "sync" ) 如你所见,Go 语言中 导入的包,必须得用双引号包含,在这里吐槽一下. 2. 使用别名 在一些场

  • 详解R语言中生存分析模型与时间依赖性ROC曲线可视化

    详解R语言中生存分析模型与时间依赖性ROC曲线可视化

    R语言简介 R是用于统计分析.绘图的语言和操作环境.R是属于GNU系统的一个自由.免费.源代码开放的软件,它是一个用于统计计算和统计制图的优秀工具. 人们通常使用接收者操作特征曲线(ROC)进行二元结果逻辑回归.但是,流行病学研究中感兴趣的结果通常是事件发生时间.使用随时间变化的时间依赖性ROC可以更全面地描述这种情况下的预测模型. 时间依赖性ROC定义 令 Mi为用于死亡率预测的基线(时间0)标量标记. 当随时间推移观察到结果时,其预测性能取决于评估时间 t.直观地说,在零时间测量的标记值应该

  • 详解R语言中的多项式回归、局部回归、核平滑和平滑样条回归模型

    详解R语言中的多项式回归、局部回归、核平滑和平滑样条回归模型

    在标准线性模型中,我们假设 .当线性假设无法满足时,可以考虑使用其他方法. 多项式回归 扩展可能是假设某些多项式函数, 同样,在标准线性模型方法(使用GLM的条件正态分布)中,参数  可以使用最小二乘法获得,其中  在  . 即使此多项式模型不是真正的多项式模型,也可能仍然是一个很好的近似值 .实际上,根据 Stone-Weierstrass定理,如果  在某个区间上是连续的,则有一个统一的近似值  ,通过多项式函数. 仅作说明,请考虑以下数据集 db = data.frame(x=xr,y=y

  • 详解R语言中的表达式、数学公式、特殊符号

    详解R语言中的表达式、数学公式、特殊符号

      在R语言的绘图函数中,如果文本参数是合法的R语言表达式,那么这个表达式就被用Tex类似的规则进行文本格式化. y <- function(x) (exp(-(x^2)/2))/sqrt(2*pi) plot(y, -5, 5, main = expression(f(x) == frac(1,sqrt(2*pi))*e^(-frac(x^2,2))), lwd = 3, col = "blue") library(ggplot2) x <- seq(0, 2*pi, b

  • 详解C语言中不同类型的数据转换规则

    详解C语言中不同类型的数据转换规则

    不同类型数据间的混合运算与类型转换 1.自动类型转换 在C语言中,自动类型转换遵循以下规则: ①若参与运算量的类型不同,则先转换成同一类型,然后进行运算 ②转换按数据长度增加的方向进行,以保证精度不降低.如int型和long型运算时,先把int量转成long型后再进行运算 a.若两种类型的字节数不同,转换成字节数高的类型 b.若两种类型的字节数相同,且一种有符号,一种无符号,则转换成无符号类型 ③所有的浮点运算都是以双精度进行的,即使是两个float单精度量运算的表达式,也要先转换成double

  • 详解Go语言中的数据类型及类型转换

    目录 1.基本数据类型 2.基础数据类型转换 3.基本数据类型转为字符串 4.strconv的使用 5.字符串转为基础类型 1.基本数据类型 数据类型有很多,先研究一下基础的,例如:布尔型.数字类型.字符串类型. 数字类型有uint8.uint16.uint32.uint64.int8.int16.int32.int64(uint和int区别在于uint为无符号整数,即只支持正数,不支持负数形式) 数字浮点型有fload32.float64.complex64.complex126(后面两个均为

  • 详解Go语言中的作用域和变量隐藏

    详解Go语言中的作用域和变量隐藏

    目录 前言 包隐藏 全局变量 类型强制 闭包 := 的情况 总结 前言 变量隐藏在 Go 中可能会令人困惑,让我们尝试弄清楚. package main import ( "fmt" "io/ioutil" "log" ) func main() { f, err := ioutil.TempFile("", "") if err != nil { log.Fatal(err) } defer f.Clos

  • 详解Go语言中泛型的实现原理与使用

    目录 前言 问题 解决方法 类型约束 重获类型安全 泛型使用场景 性能 虚拟方法表 单态化 Go 的实现 结论 前言 原文:A gentle introduction to generics in Go byDominik Braun 万俊峰Kevin:我看了觉得文章非常简单易懂,就征求了作者同意,翻译出来给大家分享一下. 本文是对泛型的基本思想及其在 Go 中的实现的一个比较容易理解的介绍,同时也是对围绕泛型的各种性能讨论的简单总结.首先,我们来看看泛型所解决的核心问题. 问题 假设我们想实现

随机推荐