博客昵称：吴NDIR
个人座右铭：得之淡然，失之坦然
作者简介：喜欢轻音乐、象棋，爱好算法、刷题
其他推荐内容
计算机导论速记思维导图
五种排序算法
二分查找入门讲解今天让我们聊一下双指针吧！在一些算法中，使用双指针可以使时间复杂度得到很大的优化。
索引
- 概念
- 引例
- 讲解
概念
- 双指针是指在某些问题中，我们需要在数组、字符串或其他数据结构中使用两个指针（通常指向不同位置），以便我们可以同时操作它们，并解决特定的问题。
- 问题：假设我们要在已排序的数组中查找两个数，使它们的和为一个特定的目标值（target）。
| 小吴去市场买鱼，它应该怎么从已有的稽币中拿出两张付给老板？ |
|---|
 |
- 从问题中我们可以知道给定的数组[2,4,5,8,20]以及target=13,可能比较直接的思路就是暴力破解
- 暴力破解的思路是遍历每对数，直到找到两个数等于目标和或者已经遍历完所有可能的数对。
- 具体地，可以使用两个嵌套循环，外层循环从数组的第一个元素开始遍历，内层循环从外层循环中的元素的下一个元素开始遍历，直到遍历完整个数组，这样就可以找出两个元素之和等于目标和的情况。
- 在代码实现中，当找到两个元素之和等于目标和的情况时，直接输出这两个元素并返回，否则说明在数组中找不到所需的两个数，则输出“找不到”。
 |
|---|
| 但是，这种暴力解法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，因为需要嵌套两层循环，因此一旦输入的数组很大，算法所需要的时间也会随之增大。因此在处理大规模问题时，这种暴力解法通常不是一个好的选择. |
- 更好的选择是使用优化算法，例如双指针。
- 首先将两个指针指向数组的两端，即一个指针指向数组的第一个元素，另一个指针指向数组的最后一个元素。
- 接着，根据两个指针所指向元素的和与目标和的大小关系来移动指针。如果两个元素的和小于目标和，则将指向较小元素的指针右移，寻求更大的元素。如果两个元素的和大于目标和，则将指向较大元素的指针左移，寻求更小的元素。如果两个元素的和等于目标和，则直接返回这两个元素。
 |
|---|
| 此双指针算法的时间复杂度为 O(n)，因为将两个指针移动到最中间的时候问题必定会被解决。和无序数组的暴力解法相比，使用双指针算法可以有效地提高查找效率，适用于较大的数组，并且避免了需要嵌套的循环，提高程序的运算效率。 |
| 对比：我们可以看到，当数组元素较多时，双指针的优势就显露出来了。 |
 |
代码实现
void find(int arr[], int n, int targetSum) { int left = 0, right = n - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == targetSum) { printf("这两个数分别是 %d 和 %d", arr[left], arr[right]); return; } else if (sum < targetSum) { left++; } else { right--; } } printf("不存在两个数之和等于目标值");}- 示例
int main() { int arr[] = {2, 3, 5, 7, 11};//例子 int n = sizeof(arr) / sizeof(arr[0]); int target = 10;//目标值 find(arr, n, target); return 0;}- 结果
引例
- 题目描述：给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
示例1
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例2
输入: nums = [0]
输出: [0]
讲解
- 这道题目的思路是使用双指针来遍历整个数组，其中一个指针left表示当前非零元素应该被放置的位置，另一个指针right则用来遍历整个数组。当right指向一个非零元素时，就将它与left指向的位置的元素进行交换，然后left向后移动一位，以便下一个非零元素可以被放置在正确的位置。当right遍历完整个数组时，left的位置右边应全为0。以下是步骤：
- 用两个指针left和right初始化为0；
- 遍历数组，当nums[right]不为0时，就将nums[left]与nums[right]交换，并将left向后移动一位；
- 遍历完整个数组后，数组中所有的0都已经移动到了末尾，完成。
示例代码
//交换对应元素void swap(int *a, int *b) { int t = *a; *a = *b, *b = t;}void move(int *nums, int numsSize) { int left = 0, right = 0; while (right < numsSize) { //当nums[right]不为0时 if (nums[right]) { swap(nums + left, nums + right); left++; } right++; }}