首页 > 其他分享 >双指针

双指针

时间:2023-11-19 14:55:25浏览次数:18  
标签:target int sum numbers 数组 指针

一、双指针介绍

一般来说是使用两个指针(大多数情况是使用的两个变量)来对一个对象进行处理,两个指针指向不同的元素,然后进行比较从而解决问题

可以用于优化暴力算法的时间复杂度

例如:给你一个已近排好序的数组v,现在需要你删除数组中的重复元素,并输出删除后的数组的长度

当然你可以的直接使用unique直接去重然后输出输出数组的大小,这里我们使用不同的方法去做并且保证O(n)的复杂度。

思路:我们只需要在遍历数组的时候不断记录长度,当我们遇到相同的值的时候直接跳过就行,可以这样做的原因是题目给出了数组是已经排好序的了

这里我们可以定义两个变量 i  = 1和 j = 0,一个在前一个在后那么对于数组 v 就是v[i]和v[j],通过比较这两个值是否相等来确定是否要跳过,不跳过就更新v[j]的值,最后输出 j + 1 即可。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    //先确定数组长度
    int len = v.size();
    int j = 0;
    for (int i = 1; i < len ; i++)//开始遍历
    {
        if(v[i] != v[j]){//不断的比较一前一后的值是否相等
          j++;
         v[j] = v[i];
        }
    }
    cout << j + 1;
}    

通过这个题我们可以体会到,i 和 j就像两个指针指向的是数组v的不同位置,然后通过比较得到结果

二、相向双指针

定义的两个指针王同一个方向走,就比如一个数组nums,我们有L和R两个指针分别对应数组的头和尾,然后他们都要往中间走,就是相向双指针。

例如:leetcode163

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1  index2

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

思路:如果你采用的是暴力,那么时间复杂度是O(n2),我们可以重点利用一下这个“非递减顺序排列”,对于一个排好序的数组采用双指针是可以将时间复杂度优化到O(n)

具体的就是定义两个指针L = 0和R  = number.length() - 1 对应数组的头和尾,然后开始遍历进行判断

1.numbers[l] + numbers[r] == target直接就break出去得到答案

2.numbers[l] + numbers[r] > target,因为数组是升序排列的,那么就说明最大的加最小的比目标值大,所以我们要将最大值减小,即R -= 1

3.numbers[l] + numbers[r] < target,同上,但是这次发现的是比目标值还小,所以我们要将最小值增大,即L += 1

代码如下:

class Solution
{
public:
    std::vector<int> twoSum(std::vector<int> &numbers, int target)
    {
        std::vector<int> ans;
        int l = 0, r = numbers.size() - 1;
        while(l <r){
            if(numbers[l] + numbers[r] == target)
            break;
            if (numbers[l] + numbers[r] > target)
                r -= 1;
            if (numbers[l] + numbers[r] < target)
                l += 1;
        }
    //这里答案加一是因为题目要求的是下标从1开始
        ans.push_back(l + 1);
        ans.push_back(r + 1);
        return ans;
    }
};

 三、滑动窗口

它属于双指针中比较重要的一个概念。顾名思义,对于一个数组我们定义两个指针那么这两个指针之间的数就类似被包含在一个窗口中,接下来我们不断地移动左右指针,使得这个窗口可以向右向左滑动。

例如:我们给出一个长度为N的数组和一个整数K,现在让你从数组中找出一个长度为K的子数组,并且要求这个子数组和的值是最大的。

N = {1,9,8,6,4,7,8} , k = 2,那么答案就是{9,8}

思路:我们分别定义两个指针L 和 R ,这个时候我们的窗口就定义好了即[ L , R]。现在我们需要滑动这个窗口,每次向右滑动一位这个窗口就变为了[ L + 1 , R + 1],那么对于这个题而言,初始的窗口就是

[0, k - 1]。sum就是这个窗口内的和,当我们向右滑动的时候,窗口变为了[1, k],sum增加了N[k],减小了N[0],依次类推,最后我们就可以得到答案

代码如下:

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {1, 9, 8, 6, 4, 7, 8};
    int index = 0;//用index来记录下我们最大子数组的左边界
    int n = v.size(), k = 2;
    int sum = 0,total = 0;
    for (int i = 0; i < n; i++){
        sum += v[i];//从0这个位置开始滑动,不断增加v[i]
        if(i >= k - 1){//当到达K - 1的时候就表示确定了一个长度为K的子数组
            if(sum > total){//判断一下当前的子数组的和是不是最大的
                total = sum;//更新子数组的和
                index = i - k + 1;//记录下边界
            }
            sum -= v[i - k + 1];//更新滑动后sum的值
        }
    }
    while(k--){
        cout << v[index++] << " ";    
    }
    return 0;
}

 

以上就是基本的双指针的使用。

 

标签:target,int,sum,numbers,数组,指针
From: https://www.cnblogs.com/linx000/p/17841032.html

相关文章

  • c语言 指针的赋值
    @TOC前言如果一个指针指向一个变量的地址,如何通过指针来改变该变量的值呢?一、指针的赋值例如:int*p;inta=3,b=4;p=&a;//指针p指向变量a的地址。p=&b;//指针p重新指向变量b的地址。二、注意点指针变量也是变量,可以以装别的地址,但是要是同类型的。重新赋值,也叫......
  • C语言指针的应用场景
    C语言指针的应用场景指针是C语言的精华和灵魂,不懂指针,基本等同于不会C语言。掌握指针,让学会C语言不再成为梦想而成为现实。指针基本上有三大类:指向数据的指针指向函数的指针泛型指针(void*)指针的应用场景可以分为以下10类:-1.与函数相关的使用-1.1在函数中用作输出......
  • 引用与指针
    引用只是给已经存在的变量赋一个别名,通过此别名操作变量与通过变量本名操作是一样的效果。为一个变量声明了引用后该变量就可通过两个名称来操作了。例如:inta=10;int&b=a;这样之后通过a与b均可来操作存储10的这块地址空间。而指针是一种变量类型,可被视为与int、char......
  • C++ 指针学习笔记
    C++指针学习笔记引入指针是什么指针是一个变量,其值为另一个变量的地址。指针声明的一般形式为:type*ptr_name;type是指针的基类型,ptr_name是指针的名称,*用来指定一个变量是指针对于一个指针,需要明确四个方面的内容:指针的类型、指针所指向的类型、指针的值(指针所指向的......
  • 指针网络原理分析
    不明确的地方,请看原文:指针网络一些难理解的关键词combinatorialproblem(组合问题):组合问题的目标是在一组有限集合中找出能够同时满足一组约束的一个满意解,在本文的语境下,是指对于给定的词元输入序列,找出能够满足一组约束的词元输出序列,作为满意解。token(词元)在本文中,词元是......
  • 函数名其实就是指向函数体的指针
    D选项会立即执行:因为setTimeout()会先判断第一个参数是否为「function」,如果不是,则会尝试将它当作字串处理。换句话说,会将checkState()执行后的回传值转为字符串,没有回传值,那就是undefined,于是变成window.setTimeout(”undefined",10000)于是10000ms到了就什么事都没发生。se......
  • HashMap集合的map.values()返回的Collection集合执行add方法报空指针问题
    一、方法1、privateCollection<String>setPermissionTenant(List<SysPermission>ls,inttenantId){//循环两次第一次设置ID和tenantId第二次设置pidMap<String,String>map=newHashMap<>();for(SysPermissionp:ls){......
  • 指针输入
    首先,用scanf对指针进行输入的时候,不要对指针加&然后,对指针进行输入时,最好先把指针指向一个明确的地址,比如#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intmain(){ intp; int*a=&p; scanf("%d",a); return0;}最好不要#include<bits/stdc++.......
  • 直接对函数传递指针
    首先来看一看这个代码这个代码输出的是2,即函数里面的c的值就是b的值,为主函数里面a这个变量的地址,所以a被改变了再来看一看这个代码这个代码输出的是1,就是b所指向的地址的内容没有被修改,所以c也是一个形参,他的值就是b的值(a的地址),但是c的值被改变了(变成了全局变量x的地址)不会导......
  • 第10章 数组和指针
    1、例如:intarray[6]={1,2,3,4,5};,array[n],数组长度为5,n取值范围[0,n-1],就是1-5的地址;2、指针指代数组:#include<stdio.h>intmain(){/*带有5个元素的整型数组*/doublebalance[5]={1000.0,2.0,3.4,17.0,50.0};double*p;inti;......