双指针算法分类
二、相向双指针示例 ( 有效回文串 )
一、双指针算法分类
----
面试时经常遇到 限制算法复杂度为
O ( n )
的情况 , 就需要使用以下算法 :
双指针算法 : 设置两个指针 ( 索引..., 然后对比是否相等 ;
但是如果添加了上述要求 , 就需要处理大小写 , 特殊字符问题 , 有两种方案 :
创建新字符串 , 过滤掉大小写及特殊字符干扰, 然后翻转字符对比 , 这样会增加额外空间开销...;
推荐使用双指针算法 , 一边进行过滤 , 一边进行对比 ;
设计两个指针 , 分别指向字符串的最左侧 和 最右侧 ;
每次遍历 , 都要进行 两个指针的下标判断 , 否则就会导致下标访问越界 ;...isValid(s.charAt(right))) {
right --;
}
// 对比两个指针指向的字符, 如果不相等...isEqual(s.charAt(left), s.charAt(right))) {
return false;
}