力扣双指针刷题（算法日记）

力扣双指针刷题（算法日记）

我要做天下第一的枪仙！——司空长风

双指针心法：

    双指针的精髓在于利用题目的单调性或者依照贪心的思路，对原来的基础代码进行一个优化，一般是优化为大On的时间复杂度。所以，使用双指针的时候，一般要先写出基础代码，然后用双指针的方法进行一个优化，双指针只是一层皮，看破题目的单调性条件或是找到贪心的思路才是解题的关键。

    常见双指针类型：

1.快慢指针；

2.同向指针；

3.对撞指针；

4.其他。。。。。。

开始

1.力扣

922. 按奇偶排序数组 II

给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2：

输入：nums = [2,3]
输出：[2,3]

提示：

• 2 <= nums.length <= 2 * 104
• nums.length 是偶数
• nums 中一半是偶数
• 0 <= nums[i] <= 1000

进阶：可以不使用额外空间解决问题吗？

实现代码1

思路：用一个变量odd指向奇数（初始为1）dou指向偶数（初始为0） 然后盯着最后一个元素看，如果是奇数，那么和odd指向的变量交换，同时odd指向下一个奇数，偶数同理，当odd或者dou有一个越界了（指向的位置大于等于length）就说明奇数或者偶数已经摆好了，因为奇偶个数相同，所以另一者也一定摆好了，这个时候的数组即符合要求。

class Solution {public int[] sortArrayByParityII(int[] nums) {int odd=1,dou=0,p=nums.length-1,t;while(odd<nums.length&&dou<nums.length){if(nums[p]%2==0){t=nums[dou];nums[dou]=nums[p];nums[p]=t;dou+=2;}else{t=nums[odd];nums[odd]=nums[p];nums[p]=t;odd+=2;}}return nums;}
}

代码2  另一个版本 思路一样 

class Solution {public int[] sortArrayByParityII(int[] nums) {int n=nums.length;for(int odd=1,dou=0;odd<nums.length&&dou<nums.length;){if((nums[n-1]&1)==1){swap(nums,n-1,odd);odd+=2;}else{swap(nums,n-1,dou);dou+=2;}}return nums;}public static void swap(int nums[],int i,int j){int t;t= nums[i];nums[i]=nums[j];nums[j]=t;}
}

2.力扣

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

这个题实现方法有很多，看你怎么优化了。

咱们用双指针就可以达到On的时间复杂度捏。

涉及到一点小技巧和小结论

一个很丑的示意图

我们定义一个环，从0号位置3开始往下走，下一次的位置的下标就是当前元素的值。

比如 从下标0开始对应元素是3，那就找到下标3对应元素，对应元素是4，那就找到下标4对应元素.....最终形成一个环。那我们只需要找到入环节点就行了，那一定是重复元素。

  设置快慢指针，快指针一次走两步，慢指针一次走一步，都从0出发。

快慢指针一定会相遇。

比如

        1    2    3     4   5

快    4    3    4    3

 慢   3     4    2    3

快慢指针在3处相遇

这个时候，把快指针返回起点，并且让他一次走一步，慢指针还是一次走一步

那么再次相遇时必定是入环节点(结论）

然后就可以写代码了

class Solution {public int findDuplicate(int[] nums) {if(nums==null||nums.length<2)return -1;int f=nums[nums[0]],s=nums[0];//快指针一开始先走两步，慢指针一开始先走一步while(s!=f)//相遇{f=nums[nums[f]];s=nums[s];}f=0;//快指针返回起点while(s!=f)//再次相遇{f=nums[f];s=nums[s];}return s;//返回快慢指针都可以}
}

3.力扣

42. 接雨水 经  典  老  番

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

思路，我只要找到每一个格子能装的最大雨水数目，然后把他们加起来，就是总共能装的雨水数目了。

那么怎么找到某个格子能装的最大雨水数目呢？

发现只要找到这个格子两边的最大高度，取个短板，减去这个格子本身的高度，就可以实现了

代码1（原始思路 未使用双指针 ）

class Solution {public int trap(int[] height) {int n=height.length;int ans=0,cnt=0;int lmax[]=new int[n];//记录左侧最大值int rmax[]=new int[n];//记录右侧最大值int max=height[0];for(int i=0;i<n;i++){max=Math.max(max,height[i]);lmax[i]=max;}//初始化max=height[n-1];for(int i=n-1;i>=0;i--){max=Math.max(max,height[i]);rmax[i]=max;}//初始化for(int i=1;i<n-1;i++){cnt=Math.min(rmax[i],lmax[i])-height[i];ans+=cnt;}return ans;
}
}

那么能不能使用双指针优化捏？

可以哒。

我们想  有没有不构建两个辅助数组，也可以达到找到两侧最大值的做法呢

可以用两个指针模拟一下

使用对撞指针，ab 比较大小，从小的那一个a开始计算雨水量，因为a是在队头，所以边界方向一定没有比他更小的高度，那么a后面那个高度接到的水一定与a持平，所以水量可以计算 ，同理 往后推进。。。直到两个指针相邻或相撞

coding

class Solution {public int trap(int[] height) {int n=height.length;int ans=0,cnt=0;int l=1,r=n-2,lmax=height[0],rmax=height[n-1];while(l<=r){if(lmax<=rmax){cnt=Math.max(lmax-height[l],0);lmax=Math.max(lmax,height[l++]);ans+=cnt;}else{cnt=Math.max(rmax-height[r],0);rmax=Math.max(rmax,height[r--]);ans+=cnt;}}return ans;
}
}

4.力扣

881. 救生艇

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

提示：

• 1 <= people.length <= 5 * 104
• 1 <= people[i] <= limit <= 3 * 104

这题跟之前写的小猫的一道题有点像，但这个数据量......暴搜很可能暴死

而且一个船最多载两个人，所以是可以考虑其他方法的。

贪一下，每次找一个最轻的和最重的放在一起，如果超重，就找第二重的，如果能放下，就是最优解了。。。

貌似可以排个序，然后用双指针模拟一下。

试试吧

代码

class Solution {public int numRescueBoats(int[] people, int limit) {int l=0,r=people.length-1;Arrays.sort(people);int ans=0;while(l<=r){if(people[l]+people[r]<=limit){l++;r--;}else{  r--;}ans++;}return ans;}
}

时间复杂度已经是最优了捏。