双指针算法c++

### 关于C++中双指针算法的实现 在C++编程中，双指针是一种常见的算法设计模式，主要用于解决涉及数组、链表或其他线性数据结构的问题。它通常通过两个索引或变量来遍历数据集的不同部分，从而优化时间复杂度。 #### 双指针的基本概念 双指针并不总是严格意义上的指针类型（`*`），它可以是数组下标或者其他形式的迭代器[^2]。其核心思想在于利用两个位置标记协同工作，减少不必要的重复计算。 以下是几个典型的双指针应用场景及其对应的代码示例： --- #### 示例一：移除指定值后的数组长度 给定一个整数数组 `nums` 和一个目标值 `val`，删除所有等于该值的元素并返回新数组的长度。 ```cpp #include <vector> using namespace std; int removeElement(vector<int>& nums, int val) { int slow = 0; // 慢指针用于记录有效元素的位置 for (int fast = 0; fast < nums.size(); ++fast) { // 快指针用于扫描整个数组 if (nums[fast] != val) { nums[slow++] = nums[fast]; // 将不等于val的元素移动到前面 } } return slow; } ``` 上述代码展示了如何使用快慢指针技术高效地原地修改数组[^1]。 --- #### 示例二：寻找有序数组中的两数之和 假设输入是一个升序排列的整数数组 `numbers` 和一个目标值 `target`，找到两个数使得它们相加的结果为目标值，并返回这两个数的索引。 ```cpp #include <vector> using namespace std; vector<int> twoSum(const vector<int>& numbers, int target) { int left = 0, right = numbers.size() - 1; // 定义左右指针 while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) { return {left + 1, right + 1}; // 返回结果（注意题目可能要求从1开始计数） } else if (sum < target) { ++left; // 如果总和小于目标，则右移左指针增大数值 } else { --right; // 如果总和大于目标，则左移右指针减小数值 } } return {}; // 若无解则返回空集合 } ``` 此代码片段体现了双指针法在处理排序数组时的优势——无需额外空间即可完成操作。 --- #### 示例三：“快乐数”的判断逻辑 对于任意正整数 n ，如果反复替换为各位数字平方和最终会进入循环或者达到固定点1，则称为“快乐数”。虽然这里并未直接采用传统意义下的指针对象，但依然遵循了双指针的核心理念即设置两个速度不同的游标逐步逼近结论。 ```cpp bool isHappy(int n) { auto get_next = [](int num)->int{ int total_sum=0; while(num>0){ int d=num%10; num /=10 ; total_sum +=d*d; } return total_sum; }; int slow=n , fast=get_next(n); while(fast!=1 && slow!=fast ){ slow=get_next(slow); // 移动一次 fast=get_next(get_next(fast)); // 移动两次 } return fast==1 ; // 判断条件成立与否 } ``` 在这里，“慢跑者”每次只前进一步而“快速选手”每轮跳跃两步直至相遇为止。 --- ### 总结 以上三个例子分别演示了不同类型的双指针应用方式，无论是实际物理地址上的指针还是抽象层面的概念化表达均能体现出这一技巧的强大功能与灵活性。