利用双指针技巧来解决七道与数组相关的题目。
- 两数之和 II - 输入有序数组： 给定一个按升序排列的数组，找到两个数使它们的和等于目标值。可以使用双指针技巧，在数组两端设置左右指针，根据两数之和与目标值的大小关系移动指针。
- 删除有序数组中的重复项： 给定一个有序数组，原地删除重复出现的元素，使每个元素只出现一次，并返回新的长度。利用双指针技巧，一个指针用于遍历数组，另一个指针指向新数组的末尾。
- 移除元素： 给定一个数组和一个值，原地移除数组中所有等于该值的元素，返回新数组的长度。同样利用双指针技巧，一个指针用于遍历数组，另一个指针用于记录非目标值的位置。
- 移动零： 给定一个数组，将所有的 0 移动到数组的末尾，同时保持非零元素的相对顺序。使用双指针技巧，一个指针遍历数组，另一个指针记录非零元素的位置，并将非零元素依次移到前面。
- 反转字符串： 反转给定的字符串。利用双指针技巧，一个指针从数组的开头向后移动，另一个指针从数组的末尾向前移动，依次交换两个指针指向的元素。
- 最长回文子串： 找到给定字符串中的最长回文子串。作者通过介绍中心扩散法，结合双指针技巧，在遍历过程中寻找回文子串的中心点。
- 删除排序链表中的重复元素： 删除排序链表中重复的元素，使得每个元素只出现一次。使用双指针技巧，一个指针遍历链表，另一个指针负责删除重复元素
一、反转字符串
题目描述
写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
代码语言：javascript复制输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]示例 2：
代码语言：javascript复制输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]提示：
1 <= s.length <= 105s[i]都是 ASCII 码表中的可打印字符
解题技巧及代码
代码语言：javascript复制一般编程语言都会提供
reverse函数，其实这个函数的原理非常简单可以利用双指针 从字符串两端开始先中间移动，依次交换字符串的每个字母即可。
class Solution {
public void reverseString(char[] s) {
int l=0,r=s.length-1;
char temp;
while(l<r){
temp=s[l];
s[l]=s[r];
s[r]=temp;
l ;
r--;
}
}
}结果展示
二、最长回文子串
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
代码语言：javascript复制输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
代码语言：javascript复制输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
解题思路及代码
寻找最长回文串的问题可以通过中心扩展法解决，其中双指针技巧是关键。思路可以总结为以下步骤：
- 对于每个字符
s[i]，以其为中心，利用Pame(s, i, i)寻找长度为奇数的回文串。此时，中心字符即为s[i]。 - 对于相邻字符
s[i]和s[i 1]，以它们为中心，利用Pame(s, i, i 1)寻找长度为偶数的回文串。 - 在每次扩展中，更新最长回文串的长度和起始位置。
这样，通过遍历字符串，以每个字符及相邻字符为中心，不断扩展找到所有可能的回文串，最终得到最长回文串的长度和起始位置。
函数 Pame(s, l, r) 的作用是在给定字符串 s 中，以指定的左右指针 l 和 r 为中心，向两端扩展，寻找回文串。这个函数的具体实现应该考虑到奇数长度和偶数长度的情况。
class Solution {
public String longestPalindrome(String s) {
String res="";
for(int i=0;i<s.length();i ){
String res1=Pame(s,i,i);
String res2=Pame(s,i,i 1);
res=res.length() > res1.length() ? res:res1;
res=res.length() > res2.length() ? res:res2;
}
return res;
}
public String Pame(String s,int l,int r){
while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r) ){
l--;
r ;
}
return s.substring(l 1,r);
}
}结果展示
