双指针法
2023-11-02 16:10:00 1 举报AI智能生成
双指针总结
作者其他创作
大纲/内容
链表篇
206.反转链表
前后指针和一个记录指针
前后指针依次移动交换
开始后指针指向头节点，结束后指针指向空
142.环形链表II
判断有环
快慢指针相遇判断有没有环
找环入口
定义一个指针index1，在头结点处定一个指针index2
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点
N数之和
第15题. 三数之和
先对数组排序
a,left,right去重
a去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
continue;
}
// 错误去重a方法，将会漏掉-1,-1,2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue;
}
/*
if (nums[i] == nums[i + 1]) {
continue;
}
去重逻辑应该放在找到一个三元组之后
left去重，left向右移动
while (right > left && nums[left] == nums[left + 1]) left++;
right去重，right向左移动
while (right > left && nums[right] == nums[right - 1]) right--;
a = nums[i]，b = nums[left]，c = nums[right]
nums[i] + nums[left] + nums[right] > 0
三数之和大了，right向左移动
nums[i] + nums[left] + nums[right] < 0
三数之和小了，left 向右移动
其他细节
if (nums[i] > 0) {
break;
}
break;
}
第18题. 四数之和
先对数组排序
nums[k] + nums[i] + nums[left] + nums[right] == target
k去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
continue;
}
i去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
continue;
}
去重逻辑应该放在找到一个四元组之后
left去重，left向右移动
while (right > left && nums[left] == nums[left + 1]) left++;
right去重，right向左移动
while (right > left && nums[right] == nums[right - 1]) right--;
剪枝操作
k剪枝
if (nums[k] > target && nums[k] >= 0) {
break;
}
break;
}
k和i剪枝
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
break;
}
数组篇
27. 移除元素
通过两个指针在一个for循环下完成两个for循环的工作
左指针遇到要移除的元素停下，然后移动右指针，右指针移动遇到要移除的元素就继续，不是要移除的就和左指针交换元素
右指针移动遇到要移除的元素就继续，不是要移除的就和左指针交换元素
左指针遇到右指针循环结束
字符串篇
344.反转字符串
利用左右指针，移动交换两端元素
剑指Offer 05.替换空格
统计空格数量count
增加数组大小count*2
老指针遇到非空格元素，赋值给新指针，遇到空格，新指针依次加入02%
151.翻转字符串里的单词
利用双指针去空格，和27移除元素类似
0 条评论
下一页
