class Solution {
public int findPairs(int[] nums, int k) {
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) {
Arrays.sort(nums);
// 储存数对的哈希表
Map map = new HashMap<>();
// 储存遍历元素的哈希表
Set 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) {
// 特判
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);
}
}
75. 颜色分类
class Solution {
public void sortColors(int[] nums) {
//计数排序，时间复杂度为O(m+n)
int[] color = new int[3];
for(int num:nums) {
color[num]++; //将颜色叠加,储存个数
}
int k=0;
for(int j=0;j<3;j++) {
while(color[j]--!=0) {
// 依次输出个数
nums[k++]=j;
}
}
}
}
