双指针

### 双指针算法概述 双指针算法的核心在于利用两个指针来遍历数据结构，而非单一指针。这种方式能够有效降低时间复杂度，在处理数组和链表等问题上尤为突出[^1]。 #### 概念解析 指针是一种用于存储内存地址的数据类型，允许程序访问并操作特定位置上的变量或对象。在双指针模式下，通常会设置一对相互关联的指针，它们可以在不同方向移动或者保持一定距离同步前进，从而完成诸如查找、排序等任务[^2]。 #### 应用场景实例分析 ##### 场景一：寻找有序数组中的两数之和等于目标值 对于已知升序排列的整型数组`nums[]` 和给定的目标数值 `target` ，可以通过设定左端起点处的一个慢速索引 i=0 以及右端终点 j=n-1 的快速索引来进行双向扫描： 当 nums[i]+nums[j]> target，则说明当前组合过大，应减小总和；此时让j向左移一位； 反之如果小于则增大i使整体变大直至找到满足条件的一对元素为止。 ```python def two_sum_sorted(nums, target): n = len(nums) i, j = 0, n - 1 while i < j: current_sum = nums[i] + nums[j] if current_sum == target: return (i, j) elif current_sum > target: j -= 1 else: i += 1 raise ValueError('No solution found') ``` ##### 场景二：反转字符串单词顺序 另一个典型例子是在不借助额外空间的情况下颠倒句子内部各词之间的相对次序。这里可以先全部翻转整个字符序列得到逆序表达形式，再逐个调整每句话内的词语使其恢复正向显示状态。此过程同样依赖于前后两端各自设立游标p,q分别指向待交换部分边界进行迭代更新直到相遇结束循环体执行完毕即可达成目的。 ```python def reverse_words(s): s.reverse() p = q = 0 n = len(s) while True: # Move to the start of next word. while p < n and s[p] == ' ': p += 1 if p >= n: break # Find end position of this word. q = p while q < n and s[q] != ' ': q += 1 # Reverse characters within one single word range [p..q). rword_end = min(q, n) - 1 while p < rword_end: s[p], s[rword_end] = s[rword_end], s[p] p += 1; rword_end -= 1 p = q return ''.join(s).strip() ```