《双指针篇》---双指针算法原理

利用数组下标来充当指针。

1.双指针算法本质：

将数据划分为三个区间，我们以移动零为例：

给定数组中。

【0，left】：全是非0元素。

【left+1，cur-1】：全是0元素。

【cur，n-1】：待处理元素。

        public void moveZeroes(int[] nums) {//定义left和right双指针。并在right<n的情况下循环。//如果nums[right] != 0则交换left和right指向的元素。//若等于零则right++。//保证left之前的数据非零。left指向第一个零。//right之后的数据待处理。int left = 0,right = 0;int n = nums.length;while(right < n){if(nums[right] != 0){int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;}right++;}}

2.拓展：快排（双指针算法是快排中最核心的一步）

快排里面最核心的一步就是数据划分这一步。

定义一个数组，我们设置一个基准元素tmp。将数组划分为两个部分。

左边全 <= tmp。 右边全 > tmp。

三个区间：

【0，left】：全是 ≤ tmp。

【left+1，cur-1】：全是 > tmp。

【cur，n-1】：待处理元素。

快排的双指针思想不适合处理很多数据都相同的情况。

后面有一道颜色划分的题目。

我们会把数组分成三块。用这个算法排序思想来解决快排是最好的解法。