双指针是一种最常见的算法技巧，通常被用在数组和链表相关的问题中，主要分为两种
快慢指针顾名思义，就是两个指针同向，一个指针移动快，一个指针移动慢。逻辑类似下面伪代码
slow = n
fast = m
while condition:
if condition:
slow++
fast++
当然也可以使用 for 来构建
slow = n
fast = m
for (;condition;fast++)
if (condition)
slow++
给你一个 升序排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
这里你可能会想到用哈希表去重
class Solution {
public int removeDuplicates(int[] nums) {
HashSet t = new HashSet();
int j = 0;
for(int i = 0; i < nums.length;i++){
if(t.contains(nums[i]))continue;
t.add(nums[i]);
nums[j++] = nums[i];
}
return j;
}
}
但是使用哈希表会引入额外的空间复杂度，所以不是最优的解法
考虑到是升序排序的数组，那么我们只要比较 nums[n] 和 nums[n+1] 的值是否相同，如果不相同就将元素前移动，可以通过快慢指针实现
class Solution {
public int removeDuplicates(int[] nums) {
int s = 0,f = 1;
while(f < nums.length){
if(nums[s] != nums[f]){
nums[++s] = nums[f];
}
f++;
}
return s + 1;
}
}
这里使用 nums[++s] = nums[f] 是因为不需要对比第一个元素，第一个元素位置肯定不会变
0x01 27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
这里显然可以使用快慢指针
class Solution {
public int removeElement(int[] nums, int val) {
int s = 0,f = 0;
while(f < nums.length){
if(nums[f] != val){
nums[s++] = nums[f];
}
f++;
}
return s;
}
}
左右指针，就是两个指针同时像内移动或者向外移动
- 向内移动，最常见的就是二分查找
- 向外移动
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
因为是单调递增的所以很自然的就可以想到使用左右双指针，时间复杂度为 O(n)
class Solution {
public int[] twoSum(int[] numbers, int target) {
int lf = 0, rg = numbers.length - 1;
while(lf < rg){
long sum = numbers[lf] + numbers[rg];
if(sum == target){
return new int[]{lf+1,rg+1};
}else if(sum < target){
lf++;
}else{
rg--;
}
}
return new int[]{};
}
}
0x01 344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
最直观的方式就是左右双指针，互换，然后指针同时移动
class Solution {
public void reverseString(char[] s) {
int lf = 0,rg = s.length - 1;
while(lf < rg){
char l = s[lf];
char r = s[rg];
s[lf] = r;
s[rg] = l;
lf++;
rg--;
}
}
}
在此基础上，如果碰到类似交换元素还可以使用异或(相同为 0 不同为 1)
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while(left < right){
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}
}
s[left] ^= s[right]等价于s[left] = s[left] ^ s[right]s[right] ^= s[left]等价于s[right] = s[right] ^ s[left] = s[right] ^ s[left] ^ s[right] = s[left]s[left] ^= s[right]等价于s[left] = s[left] ^ s[right] = s[left] ^ s[right] ^ s[left] = s[right]
0x02 5. 最长回文子串
references