---

一般使用的双指针;

• 对撞指针:在一段数据中的开头和结尾,两个指针分别出发;
• 快慢指针:两个指针从左端同时出发; 一个指针移动快,一个指针移动慢;

练习使用

1.力扣[344]反转字符串

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。
输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，
你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]提示：
1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {public void reverseString(char[] s) {//简易对撞指针;int left  =0;int right =s.length-1;while(left<right){//交换两指针对应的字符;char temp = s[left];s[left]   = s[right];s[right]  = temp;  left  ++;right --;} }
}

---

2.力扣345:反转字符串中的元音字母

原题位置:反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。示例 1：
输入：s = "hello"
输出："holle"示例 2：
输入：s = "leetcode"
输出："leotcede"提示：
1 <= s.length <= 3 * 105
s 由 可打印的 ASCII 字符组成来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {public String reverseVowels(String s) {char[] c = s.toCharArray();//简易对撞双指针;int left  = 0;int right = c.length-1;//仅对元音字母:'a' 'e' 'i' 'o' 'u'反转;while(true){//需要验证当前字符是否为元音字母;while(left < c.length && !isYuanYin(c[left])){left++;}while(right>=0 && !isYuanYin(c[right])){right--;}if(left <right){//交换方法;swap(c,left,right);left++;right--;}else{//若不符,结束当前的循环;break;}}//结束;return new String(c);}//判断是否为元音字母;private boolean isYuanYin(char s){if(s=='a'||s=='e'||s=='i'||s=='o'||s=='u'||s=='A'||s=='E'||s=='I'||s=='O'||s=='U'){return true;}return false;   }//交换两个元素;private void swap(char[] c,int a,int b){char temp = c[a];c[a] = c[b];c[b] = temp;}
}

---

3.力扣125:验证回文串

原题位置:验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串提示：
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用对撞双指针解决;

class Solution {public boolean isPalindrome(String s) {int n = s.length();//特殊用例排除;if(s==null || n == 0){return true;}//大写转小写,其他字符忽略;s = s.toLowerCase();//对撞指针;int left = 0;int right = n-1;while(left<right){//使用isLetterOrDigit方法去除非字母和数字的;while(left<right && !Character.isLetterOrDigit(s.charAt(left))){left++;}while(left<right && !Character.isLetterOrDigit(s.charAt(right))){right--;}//若不匹配则直接退出;if(s.charAt(left)!=s.charAt(right)){return false;}//指针顺利移动;left++;right--;}return true;}
}

---

4.力扣: 两数之和 II - 输入有序数组

原题位置:两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列，
请你从数组中找出满足相加之和等于目标数 target 的两个数。
如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，
则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

同样可使用对撞指针解决;

class Solution {public int[] twoSum(int[] numbers, int target) {//使用简易对撞指针;int left  = 0;int right = numbers.length-1;while(left<right){int sum = numbers[left] + numbers[right];//若相等,则直接输出;if(sum == target){return new int[]{left+1,right+1};}else if(sum<target){//若当前和较小;向右移动左指针;left++;}else{right--;}}//若没找到返回-1,-1;return new int[]{-1,-1};}
}    

---

5.力扣[11] 盛水最多的容器问题

原题位置:

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。
在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1]
输出：1示例 3：
输入：height = [4,3,2,1,4]
输出：16示例 4：
输入：height = [1,2,1]
输出：2提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

同样也是对撞指针解决;

class Solution {public int maxArea(int[] height) {int n = height.length;//使用双指针;int left  = 0;int right = n-1;//结果;int res =0;while(left<right){//木桶短板效应;按照当前区间的最短板计算;int curWater = (right - left) * Math.min(height[left],height[right]);//注意此时还要考虑之前的水箱;res = Math.max(res,curWater);if(height[left]<height[right]){left ++;}else{right --;}}return res;}
}

---

6.力扣[15] : 三数之和

原题位置:三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。 示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]示例 2：
输入：nums = []
输出：[]示例 3：
输入：nums = [0]
输出：[]提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();int n =  nums.length;//排除特殊特例;if(n<3){return list;}//先对数组来次排序;Arrays.sort(nums);for(int i =0;i<n;i++){//假如当前的数已大于0,则直接退出;if(nums[i]>0){break;}//对于多次重复的数据,跳过循环;if(i>0 && nums[i] == nums[i-1]){continue;}//使用双指针;int left = i+1;int right = n-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]));//同时也要为左指针和右指针进行减枝;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;}
}

---

7.力扣[16] : 接近的三数之和

原题位置:最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。示例 2：
输入：nums = [0,0,0], target = 1
输出：0提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {public int threeSumClosest(int[] nums, int target) {//在之前的经典三数之和问题中,需算出三数之和为0的所有组合;//这里是要三数之和为target目标值;int n = nums.length;//数组排序;Arrays.sort(nums);//数组的前三个数之和;int initSum = nums[0]+nums[1]+nums[2];for(int i=0;i<n;i++){//同样需要双指针;int left = i+1;int right = n-1;while(left<right){int sum = nums[i]+nums[left]+nums[right];//将当前的值与目标值的相近树 比较 初始和与目标值的相近数比较;if(Math.abs(target-sum)-Math.abs(target - initSum)<0){//那么就把它赋值给当前数;initSum = sum;}else if(sum > target){//当前和已经大于目标值了;right --;}else if(sum < target){//当前和已经小于目标值;left ++;}else{//否则,直接返回目标值;return sum;}}}//返回初始操作值;return initSum;}
}

---

8.力扣[18] 四数之和

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
请你找出并返回满足下述全部条件且不重复的四元组 
[nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应，则认为两个四元组重复）：0 <= a, b, c, d < n
a、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]]提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

实际就是在三数之和外 加个循环,再找一个符合的数字;

import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> list = new ArrayList<>();int n = nums.length;if(n<4){return list;}//数组排序;Arrays.sort(nums);//同样可用双指针的做法;//首先第一个数;for(int i=0;i<n-3;i++){//其实可以在这里就排除是否可以继续查找;if( (long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target ){break;}//去除重复的数,避免再次循环;if(i>0 && nums[i] == nums[i-1]){continue;}//找后面几个数;这里其实就是三数之和的相似做法了;for(int j = i+1;j< n -2;j++){//同样地,先去重;if(j>i+1 && nums[j]==nums[j-1]){continue;}//双指针;int left  = j+1;int right = n-1;while(left<right){int sum = nums[i]+nums[j]+nums[left]+nums[right];if(sum == target){list.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--;}//其他两种情况;else if(sum < target){left++;}else{right--;}}}}return list;}
}

---

9.力扣[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 n = people.length;int left = 0;int right = n-1;int good = 0;Arrays.sort(people);while(left<=right){int sum = people[left]+people[right];//若符合限制;则运输;if(sum <= limit){//加人;left++;}//人数在减少;right--;good++;}return good;}
}

---

10.力扣[633] 平方数之和

平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5示例 2：
输入：c = 3
输出：false提示：
0 <= c <= 231 - 1

注意数据类型;

class Solution {public boolean judgeSquareSum(int c) {if (c == 0) {return true;}//双指针;右边界为数字c开方;long left = 0;long right =(long)Math.sqrt(c);while(left <= right){long temp = left*left + right*right;if(temp == c){return true;}else if(temp > c){right--;}else{left++;}}return false;}
}

---