«

C语言中双指针算法如何使用

时间:2024-4-15 08:57     作者:韩俊     分类: Java


本篇内容主要讲解“C语言中双指针算法如何使用”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C语言中双指针算法如何使用”吧!

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

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;
    }
};

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

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

标签: java

热门推荐