算法专题：双指针

目录

题目1：移动零

题目2：复写零

题目3：快乐数

题目4：最多水的容器

题目5：有效三角形的个数

题目6：两数之和为s

---

题目1：移动零

给定一个数组nums，编写一个函数将所有的0移动到数组的末尾同时保持非0元素的相对顺序。(就地实现)
示例 
散乱数组：nums{0，1，0，3，12 }==》nums{1,3，12，0，0}

算法原理：利用双指针（数组下标充当指钱）来实现数组划分

如果cur处为非0，交换dest+1和cur处的值同时两个下标向右走，开始处理dest=-1；cur=0;

实现代码：

void moveZeroes(vector<int>& nums)
{
	for (int cur = 0, dest = -1; cur < nums.size(); cur++)
	{
		if (nums[cur])
		{
			swap(nums[++dest], nums[cur]);
		}
	}
}

题目2：复写零

给定一个长度固定的整数数组arr，将该数组中出现的每个0都复写一遍，将其余元素向右平移，不开辟新空间，就地复写
示例：
{1，0，2，3，0，4，5，0}==》{1，0，0，2，3，0，0，4}

算法原理：
1.先找到最后一个复写的数
从左往右遍历cur指向第0个元素.
dest指向一1，若arr[cur]不为0，dest和cur都向后走一步若：arr[cur]为0，则dest何右走两走两步，cur向右走一步。

2.调整边界
3.从右往左完成复写

实现代码：

void doubleZeroes(vector<int>& arr)
{
	//1.先找到最后一个复写的数
	int cur = 0, dest = -1, n = arr.size();
	while (cur < n)
	{
		if (arr[cur])dest++;
		else dest += 2;
		if (dest >= n - 1)break;
		cur++;
	}
	//2.处理边界
	if (dest == n)
	{
		arr[n - 1] = 0;
		cur--; dest--;
	}
	//3.从右往右完成复写
	while (cur >= 0)
	{
		if (arr[cur])arr[dest--] = arr[cur--];
		else
		{
			arr[dest--] = 0;
			arr[dest--] = 0;
			cur--;
		}
	}
}
 
//3.快乐数

题目3：快乐数

编写一个算法来判断一个数是不是快乐数。
快乐数定义为：
1.对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,也可能是无限循环但始给达不到1如果这个过程结果为1,那么这个数就是快乐数，如果n是快乐数就返回true，不是则返回false。
1、题目解析
示例：n=19                     n=2
9²+9²=82                       2²=4
8²+2²=68                       4²=16
6²+8²=100                     1²+6²=37    
1²+0²+0²=1                    3²+7²=58......89->145->42->20...2²+0²=2

19就是快乐数 ，2不是快乐数。

解法：快慢指针

定义：

1.定义快慢指针
2.慢指针每一次向后移动一步
3.快指针每一次向后移动两步
根据鸽巢原理快慢指针最终会相遇
4.判断相遇的值即可

代码实现：

int bitSum(int n)//返回n这个数每一位上的平方和
{
	int sum = 0;
	while (n)
	{
		int t = n % 10;
		sum += t * t;
		n /= 10;
	}
	return sum;
}
bool isHappy(int n)
{
	int slow = n, fast = bitSum(n);
	while (slow != fast)
	{
		slow = bitSum(slow);
		fast = bitSum(fast);
	}
	return fast == 1;
}

题目4：最多水的容器

给定一个长度为n的整数数组height，有n条垂线，第i条钱的两个端点是(i,0)和(i,height[i])。找出其中两条线，使得它们与X轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量。

算法思想： 

代码实现：

int maxArea(vector<int>& height)
{
	int left = 0, right = height.size() - 1, ret = 0;
	while (left < right)
	{
		int v = min(height[right], height[left]) * (right - left);
		ret = max(ret, v);
		if (height[right] > height[left])left++;
		else right--;
	}
	return ret;
 
}

题目5：有效三角形的个数

给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。
示例：如nums={2，2，3，4}
输出3。
解法—：暴力校举 
解法二：利用单调性使用双指针算法。
1.对数组排序
2.当对数组进行排序后，我们选定最右边的元素作为第三边，此时，只需在其的左区间找到两个元素之和大于它两组成三角形（最小两边之和大于最大的一边）
以{2，2，3，4，5，8，9，10}为例

nums[left]为左区间的最小值，而nums[right]为左区间的最大值，若此时nums[left]与nums[right]之和小于10，则此时在数组 nums中nums[left]无法与10组成三角形;若此时nums[left]与nums[right]之和大于10，则nums[right]与其左区间内的任一元素，都可以和10构成三角形。

实现思想：

实现代码：

int triangNumber(vector<int>& nums)
{
	//1.优化
	sort(nums.begin(), nums.end());
	//2.利用双指针结合单调性快速统计
	int ret = 0, n = nums.size();
	for (int i = n - 1; i >= 2; i--)
	{
		int left = 0, right = i - 1;
		while (left < right)
		{
			if (nums[left] + nums[right] > nums[i])
			{
				ret = ret + (right - left);
				right--;
			}
			else
			{
				left++;
			}
		}
	}
	return ret;
}

题目6：两数之和为s

输入一个递增的排序数组和一个数字S，在数组中查找两个数使得它们的和正好是S，如果有多对的数字和为S，则输出任意一对即可。

解法：利用数组递增,使用双推针解决问题

1.sum>s;right--;
 2.sum 3.sum==t;return{nums[right],retunrn[left]};

代码实现：

vector<int> towSum(vector<int>& nums, int s)
{
	//1, 0, 2, 3, 0, 4, 5, 0
	int left = 0, right = nums.size()-1;
	while (left < right)
	{
		int sum = nums[left] + nums[right];
		if (sum > s)right--;
		else if (sum < s)left++;
		else return { nums[left],nums[right] };
	}
	return { -1,-1 };
}