C语言中双指针算法如何使用
本篇内容主要讲解“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;
}
};
本题思路确定后代码比较好理解，就没有分析部分了。
这两道题都是双指针的解法：第一题相当于是相邻指针，第二题则是双端指针，各有特色。
到此，相信大家对“C语言中双指针算法如何使用”有了更深的了解，不妨来实际操作一番吧！这里是蜗牛博客网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
评论