leetCode - - - 双指针
目录
1.寻找重复数（LeetCode 287）
解法一：二分查找
解法二：快慢指针
2.验证回文串（LeetCode 125）
3.三数之和（LeetCode 15）
4.四数之和（LeetCode 18）
5.x 的平方根（LeetCode 69）
6.总结
1.寻找重复数（LeetCode 287）
https://leetcode.cn/problems/find-the-duplicate-number/description/
给定一个包含 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
示例 3 :
输入：nums = [3,3,3,3,3] 输出：3
提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
解题思路：
题目要求：常量级 O(1) 的额外空间，so~用不了哈希表啦~，so~缩小范围找~，那就二分查找~
所以，先按照二分查找解题。
解法一：二分查找
class Solution {public int findDuplicate(int[] nums) {int left=1;int right=nums.length-1;while(left<right){int count=0;int mid=(left+right)/2;for(int num:nums){if(num<=mid){count++;}}if(count>mid){right=mid;}else{left=mid+1;}}return left;}
}
二分查找时间复杂度为：n（logn）
人家题目还想让你设计一个线性级时间复杂度 O(n) 的解决方案。
卷吧卷吧，官方给的解法是快慢指针。我真的栓Q，按照答案的意思，按照索引指向能够构造出一个有环路的链表，环闭合的位置就是重复的元素。按照求环路链表环的思路解这个数组题，逆天~
so~
解法二：快慢指针
class Solution {public int findDuplicate(int[] nums) {// 1、通过快慢指针的方式，在环中寻找它们的第一次相遇的节点位置// 2、定义一个慢指针，每次只会向前移动 1 步int slow = 0;slow = nums[slow];// 3、定义一个快指针，每次只会向前移动 2 步int fast = 0;fast = nums[nums[fast]];// 4、如果链表有环，那么无论怎么移动，fast 指向的节点都是有值的while (slow != fast) {// 慢指针每次只会向前移动 1 步slow = nums[slow];// 快指针每次只会向前移动 2 步fast = nums[nums[fast]];}// 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a// 一个指向相遇节点，定义为 bint b = fast;// 一个指向链表头节点，定义为 aint a = 0;// 让 a 、b 两个指针向前移动，每次移动一步，直到相遇位置// 由于有环，必然相遇// 当 b 走了 n（y + z） - y 时，b 到达了环形入口节点位置// 当 a 走了 x 步时，a 到达了环形入口节点位置// a 与 b 相遇while (a != b) {// a 指针每次只会向前移动 1 步a = nums[a];// b 指针每次只会向前移动 1 步b = nums[b];}// 6、返回 a 和 b 相遇的节点位置就是环形入口节点位置return a;}
}2.验证回文串（LeetCode 125）
https://leetcode.cn/problems/valid-palindrome/
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。
class Solution {public boolean isPalindrome(String s) {int left=0;int right=s.length()-1;while(left<right){while(left<right && !Character.isLetterOrDigit(s.charAt(left))){left++;}while(left<right && !Character.isLetterOrDigit(s.charAt(right))){right--;}// 来到这里时// 要么 left 和 right 相遇了，跳出循环// 要么 left 和 right 还没有相遇，并且它们都是指向字母或者数字if(left<right){if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))) {return false;}else{left++;right--;}}}return true;}
}3.三数之和（LeetCode 15）
https://leetcode.cn/problems/3sum/description/
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
解题思路：
1.排序数组：对输入数组进行排序，以便使用双指针方法。
2.初始化结果列表：创建一个列表来存储最终的三元组结果。
3.遍历每个元素：对于每个元素，将其作为三元组的第一个元素。
如果当前元素大于零，结束循环，因为后面的元素也大于零，不可能和为零。
跳过与前一个元素相同的元素以避免重复。
4.双指针搜索：设置两个指针，left 和 right，在当前元素后面查找其他两个元素使三数之和为零。
如果三数之和为零，记录该三元组并跳过重复元素。
根据三数之和的大小调整左右指针的位置。
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> list=new ArrayList<>();for(int i=0;i<nums.length-2;i++){if(nums[i]>0) break;if(i>0 && nums[i]==nums[i-1]) continue;int left=i+1;int right=nums.length-1;while(left<right){ int sum=nums[i]+nums[left]+nums[right];if(sum==0){//list.add(Arrays.asList(nums[i],nums[left],nums[right]));list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);while(left<right && nums[left]==nums[left+1]){left++;}while(left<right && nums[right]==nums[right-1]){right--;}left++;right--; }else if(sum<0){left++;}else {right--;}}}return list;
}
}4.四数之和（LeetCode 18）
https://leetcode.cn/problems/4sum/description/
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
四数之和和上面的三数之和解法基本一致，只是多了一层for循环，本质还是利用双指针找到最后的两个数。
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans = new ArrayList();// 边界情况判断if (nums == null || nums.length < 4) {return ans;}Arrays.sort(nums);// 获取数组的长度int len = nums.length;// 开始遍历整个数组// 1、第一层循环// nums[i] 作为四个元素当中最小的那个元素// 需要留下 nums[len - 3] 、nums[len - 2] 、nums[len - 1] 这三个元素// 所以 i 的范围是 [ 0 , len - 4 ]for (int i = 0; i <= len - 4; i++) {// 答案中不可以包含重复的四元组，所以需要执行一个去重的操作if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 如果发现当前区间中，最小的四个元素之和都大于了 target// 此时，剩下的三个数无论取什么值，四数之和一定大于 target，可以直接退出第一层循环if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}// 如果发现当前区间中，选择最大的三个数和 nums[i] 相加都小于了 target// 说明此时剩下的三个数无论取什么值，四数之和一定小于 target// 因此第一层循环直接进入下一轮，即执行 i++if ((long) nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {continue;}// 来到这里时，通过第一层循环，已经确定 nums[i] 这个数// 在 [ i + 1 , len - 1 ] 这个区间中寻找剩下的两个数// 2、第二层循环// nums[j] 作为四个元素当中第二小的那个元素// 需要留下 nums[len - 2] 、nums[len - 1] 这三个元素// 所以 j 的范围是 [ i + 1 , len - 3 ]for (int j = i + 1; j <= len - 3; j++) {// 答案中不可以包含重复的四元组，所以需要执行一个去重的操作if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}// 如果发现当前区间中，最小的四个元素之和都大于了 target// 此时，剩下的三个数无论取什么值，四数之和一定大于 target，可以直接退出第二层循环 if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}// 如果发现当前区间中，选择最大的三个数和 nums[i] 相加都小于了 target// 说明此时剩下的三个数无论取什么值，四数之和一定小于 target// 因此第二层循环直接进入下一轮，即执行 j++if ((long) nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {continue;}// 否则的话，开始去寻找剩下的两个数// 在 [ i + 1 , len - 2 ] 这个区间int left = j + 1 ;int right = len - 1;// left 和 right 不断的向内移动// 逻辑和三数之和的逻辑一样while (left < right) {// 计算这四个元素之和int sum = nums[i] + nums[j] + nums[left] + nums[right];// 发现四者之和为 0if (sum == target) {// 把这个结果记录一下ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;// 如果四者之和小于 0 ，那么说明需要找更大的数} else if (sum < target) {// left 向右移动left++;// 如果四者之和大于 0 ，那么说明需要找更小的数} else {// right 向左移动right--;}}}}return ans;}
}5.x 的平方根（LeetCode 69）
https://leetcode.cn/problems/sqrtx/description/
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
class Solution {public int mySqrt(int x) {int left=0;int right=x;while(left<=right){int mid=left+(right-left)/2;if((long)mid*mid==x){return mid;}else if((long)mid*mid<x){left=mid+1;}else{right=mid-1;}}return right;}
}6.总结
共同点和解题技巧：
1.排序和双指针：许多问题使用排序结合双指针技术来优化时间复杂度（如三数之和和四数之和）。
2.去重：在处理组合或子集问题时，常需要通过去重来避免重复结果。
3.二分查找：对某些范围的搜索问题，可以使用二分查找来提高效率。
4.边界情况：处理特殊边界情况（如数组为空、单个元素、特定条件下的快速解答）是很重要的。
5.预处理：有时候需要对数据进行预处理（如字符串的转换、过滤）以简化后续操作。
题目回顾：
1. 寻找重复数（LeetCode 287）
题目描述：给定一个包含 (n+1) 个整数的数组，其中每个整数都在 1 到 (n) 之间，找出数组中的重复数。
解题技巧：
二分查找：将问题转换为寻找一个数满足某种条件的问题。
快慢指针（Floyd 判圈算法）：通过快慢指针的方式检测循环中的重复元素。
实现思路：
快慢指针：通过设置两个指针，一个快指针和一个慢指针，找出数组中存在的循环，找到重复的数。
2. 验证回文串（LeetCode 125）
题目描述：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，并忽略大小写。
解题技巧：
双指针：使用两个指针从字符串的两端向中间移动进行比较。
预处理：将字符串转换为统一格式（小写或大写），并移除非字母数字字符。
实现思路：
使用双指针从字符串两端向中间移动，检查字符是否相等。
3. 三数之和（LeetCode 15）
题目描述：在一个整数数组中找出所有和为零的三元组。
解题技巧：
排序+双指针：先对数组进行排序，然后使用双指针技术查找符合条件的三元组。
去重：避免重复的三元组出现。
实现思路：
排序数组，然后固定一个数，使用双指针在剩下的部分查找其他两个数。
4. 四数之和（LeetCode 18）
题目描述：在一个整数数组中找出所有和为目标值的四元组。
解题技巧：
排序+双指针：先对数组进行排序，然后用两层循环固定两个数，再使用双指针查找另外两个数。
去重：避免重复的四元组出现。
实现思路：
排序数组，使用两层循环固定前两个数，使用双指针查找另外两个数。
5. x 的平方根（LeetCode 69）
题目描述：
计算非负整数 (x) 的平方根的整数部分。
解题技巧：
二分查找：在区间 [0, x] 中寻找平方根。
边界情况处理：考虑特殊情况，比如 (x = 0) 和 (x = 1)。
实现思路：
使用二分查找在区间 [0, x] 中寻找整数平方根。