标签：遍历 认识 元素 链表 查找 数组 指针
- 基本概念
双指针：通常是指在数组或链表中使用两个指针（索引）来遍历或操作数据结构。
方向：指针可以同向移动（如快慢指针），也可以相向移动（如对撞指针）。
应用场景：适用于需要遍历整个数据结构并进行某种操作的情况，如查找、排序、反转等。
- 常见类型
2.1 快慢指针
定义：两个指针从同一端开始移动，但速度不同。
应用：
链表中的环检测：快指针每次移动两步，慢指针每次移动一步，如果链表中有环，快慢指针最终会相遇。
数组中的删除元素：通过双指针重排数组，删除特定元素。
2.2 对撞指针
定义：两个指针从相对的两端开始向中间移动。
应用：
二分查找：在有序数组中查找特定元素。
两数之和问题：在有序数组中查找两个数使其和为特定值。
三数之和问题：在数组中查找三个数使其和为特定值。
- 常见问题
3.1 两数之和
问题描述：在一个有序数组中找到两个数，使其和等于给定的值。
解法：使用左右指针，从数组的两端开始，如果和大于目标值，右指针左移；如果和小于目标值，左指针右移。
3.2 反转数组
问题描述：反转数组中的元素顺序。
解法：使用左右指针，交换两端的元素，直到指针相遇。
3.3 删除重复元素
问题描述：删除数组中的重复元素，使其每个元素只出现一次。
解法：使用快慢指针，快指针遍历数组，慢指针指向新数组的末尾。
- 复杂度分析
时间复杂度：通常为 O(n)，因为双指针算法通常只需要遍历一次数组或链表。
空间复杂度：通常为 O(1)，因为只需要常数级别的额外空间
标签：遍历,
认识,
元素,
链表,
查找,
数组,
指针
From： https://www.cnblogs.com/wjhfree/p/18459303