双指针总结
532. 数组中的 k-diff 数对（前后指针）
class Solution {
public int findPairs(int[] nums, int k) {
/**
分析：
题意中是要返回不同数对的数量，那么（1,2）和（2,1）其实本质是一样的，这里规定从小到大排序，即数对是非严格递增的==》将数组排好序，利用双指针特性，在合适的时候，进行前后指针的移动
*/
Arrays.sort(nums);
int len = nums.length;
if(len < 2){
// 只有一个数，不会构成数对
return 0;
}
// 结果
int res = 0;
// 至少是两个数
int left = 0;
int right = 1;
while(left <= right && right < len){
if(nums[right] - nums[left] == k){
// 找到数对
res++;
// 下面的逻辑是解题的关键！！！
// 移动右指针并判断指针数与前一个数是否重合
do{
right++;
}while(right < len && nums[right] == nums[right-1]);
// 移动左指针并判断指针值与前一个数是否重合
do{
left++;
}while(left < right &&nums[left] == nums[left - 1]);
}else if(nums[right] - nums[left] > k){
// 移动左指针
left++;
}else{
// 移动右指针
right++;
}
// 两个指针必须对应数组中的两个数
if(left == right){
// 两指针重合，右指针走一步
right++;
}
}
return res;
}
}
注意：这种题目还可以用哈希表，在使用哈希表过程中要时刻保持对HashMap和HashSet的敏感度，其中HashMap的使用，有些储存的是值-下标，有些储存的是值-个数，有些储存的是值-值。根据题目，灵活使用！
class Solution {
public int findPairs(int[] nums, int k) {
/*
这道题其实很像two-sum的变种题，一看到两数相加等于一个target，第一个想法就是哈希表，唯一不同的点就在于，这里数对的定义(1,2)和(2,1)是同一个数对，所以核心思路就是如何去去重==》数组预先排序，定义一个储存数对的哈希表和储存遍历元素的哈希表
注意：这里是对HashSet的使用，扩充了去除重复元素的思路。
*/
Arrays.sort(nums);
// 储存数对的哈希表
Map<Integer,Integer> map = new HashMap<>();
// 储存遍历元素的哈希表
Set<Integer> set = new HashSet<>();
// 遍历元素
for(int i = 0; i < nums.length; i++){
if(set.contains(nums[i] - k)){
// set中有遍历元素，那么储存数对
map.put(nums[i],nums[i] - k);
}
// 储存遍历元素,比如有n个1，最后set中只会有一个1，达到去重目的
set.add(nums[i]);
}
// map的大小就是数对中的个数
return map.size();
}
}
925. 长按键入
class Solution {
public boolean isLongPressedName(String name, String typed) {
/**
分析：
题目的意思就是name中的一个字母可能对应typed中多个相同字母，那么这里就可以使用个一个计数变量count，当count>0时，说name中的字母出现的次数比typed中字母出现的次数还要高，就直接返回false。
当遍历完name后，若发现还没有遍历完typed，则发现typed中存在多余的字符，这时候，也是返回false，反之返回true
*/
// 特判
if(name.length() == 0 || typed.length() == 0){
return false;
}
int i = 0;
int j = 0;
while( i < name.length()){
// 定义一个计数变量count
int count = 0;
// 定义字符ch
char ch = name.charAt(i);
// 遍历name中所有ch字符
while( i < name.length() && name.charAt(i) == ch){
// 找到ch字符，+1
count++;
// 移动指针
i++;
}
// 遍历typed中所有ch字符
while( j < typed.length() && typed.charAt(j) == ch){
// 找到ch字符，-1
count--;
// 移动指针
j++;
}
// 在本轮侦查过程中，发现count>0，则返回false
if(count > 0){
return false;
}
}
// 遍历完name后，发现j不等于typed的长度，则返回false
return j == typed.length();
}
}
56. 合并区间
class Solution {
public int[][] merge(int[][] intervals) {
/**
分析：
第一想法就是对二维数组排好序，定义结果数组，对原始数组单层循环遍历，根据条件判断是否应该合并。
第一次解法的误区就是没有定义好双指针，当发生合并时，指针没有及时更新。
还有就是对最后一组数组要进行添加。
*/
if(intervals.length == 1){
return intervals;
}
// 定义结果数组和区间个数count
int[][] res = new int[intervals.length][2];
int count = 0;
// 对二维数组进行排序
Arrays.sort(intervals,(a,b) -> {return a[0] - b[0];});
// 定义初始双指针
int start = intervals[0][0],end = intervals[0][1];
// 遍历数组,从第二组开始
for(int i = 1; i < intervals.length; i++){
// 后一组区间的下界比end小
if(intervals[i][0] <= end){
// 更新指针的end界限
end = Math.max(end,intervals[i][1]);
}else{
// 合并区间
res[count][0] = start;
res[count][1] = end;
count++;
// 双指针指向新区间
start = intervals[i][0];
end = intervals[i][1];
}
}
// 添加最后一组数据
res[count][0] = start;
res[count][1] = end;
count++;
// 截取二维数组
return Arrays.copyOfRange(res,0,count);
}
}