数据结构与算法（七）数组系列——双指针在数组中的使用

深藏阁楼爱情的钟 2023-01-05 12:18 11阅读 0赞

### 文章目录 ###

*  数组 — 双指针
 *   *  1 双指针在数组中的使用
     *   *  1.1 调整数组顺序使奇数位于偶数前面
         *   *  题目
             *  思路
             *  代码
         *  1.2 和为S的两个数字
         *   *  题目
             *  思路
             *  代码
         *  1.3 和为S的人连续正整数序列
         *   *  题目
             *  思路
             *  代码

# 数组 — 双指针 #

数组是我们在开发中最常见到的数据结构了，用于按顺序存储元素的集合。但是元素可以随机存取，因为数组中的每个元素都可以通过数组索引来识别。插入和删除时要移动后续元素，还要考虑扩容问题，插入慢。

数组与日常的业务开发联系非常紧密，如何巧妙的用好数组是我们能否开发出高质量代码的关键

## 1 双指针在数组中的使用 ##

> 上面链表中提到的一类题目，主要是利用两个或多个不同位置的指针，通过速度和方向的变换解决问题。注意这种技巧经常在排序数组中使用。

### 1.1 调整数组顺序使奇数位于偶数前面 ###

#### 题目 ####

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分

#### 思路 ####

两个指针start、end，一个从前开始，一个从后开始，比较指针所指元素。

1.  若arr\[start\]为偶数，arr\[end\]为奇数，交换两个元素，start++,end–。
2.  若arr\[start\]为偶数，arr\[end\]也为偶数，end–，直至end指针所指为奇数，交换。
3.  若arr\[start\]为奇数，start++，直至start指向偶数。
4.  当start>end交换完成。

#### 代码 ####

> 若需要保证相对顺序不变，则不能用上面的写法，需要让两个指针同时从左侧开始

### 1.2 和为S的两个数字 ###

#### 题目 ####

输入一个递增排序的数组和一个数字`S`，在数组中查找两个数，使得他们的和正好是`S`，如果有多对数字的和等于`S`，输出两个数的乘积最小的。

#### 思路 ####

> 数组中可能有多对符合条件的结果，而且要求输出乘积最小的，说明要分布在两侧 比如 `3,8` `5,7` 要取`3,8`。

看了题目了，很像`leetcode`的第一题【两数之和】，但是题目中有一个明显不同的条件就是数组是有序的，可以使用使用大小指针求解，不断逼近结果，最后取得最终值。

*  设定一个小索引`left`，从`0`开始
 *  设定一个大索引`right`，从`array.length`开始
 *  判断`array[left] + array[right]`的值`s`是否符合条件
 *  符合条件 - 返回
 *  大于`sum`，`right`向左移动
 *  小于`sum`，`left`向右移动
 *  若`left=right`，没有符合条件的结果

#### 代码 ####

### 1.3 和为S的人连续正整数序列 ###

#### 题目 ####

输入一个正数`S`，打印出所有和为S的连续正数序列。

例如：输入`15`，有序`1+2+3+4+5` = `4+5+6` = `7+8` = `15` 所以打印出3个连续序列`1-5`，`5-6`和`7-8`。

#### 思路 ####

*  创建一个容器`child`，用于表示当前的子序列，初始元素为`1,2`
 *  记录子序列的开头元素`small`和末尾元素`big`
 *  `big`向右移动子序列末尾增加一个数 `small`向右移动子序列开头减少一个数
 *  当子序列的和大于目标值，`small`向右移动，子序列的和小于目标值，`big`向右移动

#### 代码 ####