🔥前言
今天带大家来学习算法中双指针的应用场景，所选题目来自牛客网 —— 免费的面试刷题神器。
牛客网界面：
剑指offer题目专栏界面：
一、最长不含重复字符的子字符串
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; } };
本题思路确定后代码比较好理解，就没有分析部分了。
这两道题都是双指针的解法：第一题相当于是相邻指针，第二题则是双端指针，各有特色。
