我的主页：2的n次方_
1. 双指针算法
双指针算法是一种在数组或字符串中常用且高效的算法技术，它通过维护两个指针（或索引）来遍历数据结构，从而解决某些问题。这种算法能够减少不必要的重复遍历，降低时间复杂度，并且往往能够使得代码更加简洁易懂。
根据指针的的移动方向可以分为同向双指针，相向双指针，快慢指针
2. 同向双指针
2.1 移动零
283. 移动零
思路：定义dest,cur两个指针，用cur从前往后遍历数组
维护三个区间 0~dest为非0元素 ， dest + 1 ~ cur -1 都为0 ，cur ~ n-1为待处理元素
class Solution {public void moveZeroes(int[] nums) {int dest = -1, cur = 0;while (cur != nums.length) {if (nums[cur] == 0) {cur++;} else {dest++;swap(nums, cur, dest);cur++;}}}
public void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}2.2 复写零
1089. 复写零
如果使用双指针从前往后进行维护，那么会把原来数组中的值覆盖掉，造成数据混乱，所以可以尝试采用从后往前覆盖的方法
思路：先找到最后一个复写的数，然后从后往前判断复写边界问题，如果最后一个复写的数为0，意味着 dest需要往后移动两位，此时就会造成越界修改，此时就需要进行判断，但不能通过 arr[cur]来判断，需要根据dest的位置来判读，因为arr[cur]为0时也存在两种情况：dest往后移动两位刚好等于数组长度或超出一个数组长度
class Solution {public void duplicateZeros(int[] arr) {//找到最后一个复写的0int dest = -1, cur = 0;while (dest < arr.length - 1) {if (arr[cur] == 0) {dest += 2;cur++;} else {dest++;cur++;}}cur--;//处理边界情况if (dest == arr.length) {arr[dest - 1] = 0;dest -= 2;cur--;}//进行复写while (cur != -1) {if (arr[cur] == 0) {arr[dest] = 0;arr[dest - 1] = 0;dest -= 2;cur--;} else {arr[dest] = arr[cur];dest--;cur--;}}}
}3. 快慢指针
3.1 快乐数
202. 快乐数
证明一定会出现循环：题中给出的数据范围是int的最大值，就按照9e9来说，每一位平方求和为729，所以一定会有重复的数据
这种形状就类似于之前做过的环形链表，那道题就是利用了快慢指针，这道题同样可以使用快慢指针，但并不是传统意义上的两个指针进行移动，而是根据对当前数字操作的次数来抽象为快慢指针
既然快乐数一定可以成环，所以只需要判断环里面的数字是否是1即可
class Solution {public boolean isHappy(int n) {int slow = n, fast = squareSum(n);while (slow != fast) {slow = squareSum(slow);fast = squareSum(squareSum(fast));}return slow == 1;}
public int squareSum(int n) {int sum = 0;while (n > 0) {int tmp = n % 10;sum += tmp * tmp;n /= 10;}return sum;}
}4. 相向指针
4.1 盛水最多的容器
11. 盛最多水的容器
如果直接进行暴力枚举出所有组合，那么一定会超时的，通过双指针可以对其进行优化
思路：先找一段区间进行分析，发现对于左右两端最小的数来说的话，继续向内模拟，无论是找到比这个数小的还是大的，都会使最终结果变小（找到小的数肯定会变小，找到大的数高度不变，宽度变小，最终还是变小），所以根据单调性，从整个区间开始，每次舍弃较小的，依次来得到不同的组合，最后比较结果最大的组合
class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1;int max = 0;while (left != right) {max = Math.max(max,(right - left) * Math.min(height[left], height[right]));if (height[left] > height[right]) {right--;} else {left++;}}return max;}
}4.2 有效三角形的个数
611. 有效三角形的个数
如果正常暴力枚举，三层循环的时间复杂度就太慢了
思路：
这里进行一个优化：先把数组排序，已经排好序的三个数中，较小的两个数之和大于最长的那条边，就可以判断为三角形还是通过双指针，从后往前，先确定一个最长的边，然后从剩下的区间中开始判断，由于已经排好序了，所以如果最小的那个数加起来就已经大于第三边，那么剩下的所有就都符合，同理，此时再把右指针左移，确定下一个区间
class Solution {public int triangleNumber(int[] nums) {int res = 0;Arrays.sort(nums);for (int cur = nums.length - 1; cur >= 2; cur--) {int left = 0, right = cur - 1;while (left < right) {if (nums[left] + nums[right] > nums[cur]) {res += right - left ;right--;} else {left++;}}}return res;}
}4.3 查找总价格为目标值的两个商品（两数之和）
LCR 179. 查找总价格为目标值的两个商品
也就是两数之和的问题，由于已经是排好顺序的数组，并且返回任意结果都行，通过使用双指针，如果left + right小于目标值，就把left左移，反之，把right右移
class Solution {public int[] twoSum(int[] price, int target) {int left = 0, right = price.length - 1;int[] res = new int[2];while (left < right) {if (price[left] + price[right] > target) {right--;} else if (price[left] + price[right] < target) {left++;} else {res[0] = price[left];res[1] = price[right];break;}}return res;}
}4.4 三数之和
15. 三数之和
思路：先进行排序，然后确定一个数，剩下的两个数按照两数之和的方法解决
去重：由于已经排好顺序了，所以当找到一个符合条件的组合之后，左右两个指针之后代表的数之后的数如果相同，那么肯定就会重复，只需要把这些数跳过去，或者使用容器去重
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length - 2; ) {//由于所有和为0，所以确定的最小的那个数必须要是负数if (nums[i] > 0) {break;}//两数之和int left = i + 1, right = nums.length - 1;while (left < right) {if (nums[left] + nums[right] < -nums[i]) {left++;} else if (nums[left] + nums[right] + nums[i] == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);ans.add(list);left++;right--;//左右两边去重while (left < right && nums[left - 1] == nums[left]) {left++;}while (right > left && nums[right + 1] == nums[right]) {right--;}} else {right--;}}//确定好的那个数去重i++;while (i + 1 < nums.length - 1 && nums[i - 1] == nums[i]) {i++;}}return ans;}
}4.5 四数之和
18. 四数之和
四数之和也就是在三数之和的基础上再确定一个数，需要注意的是，此时需要去重的点有：第一个确定的数和第二个确定的数，进行双指针算法时的left和right
class Solution {public List<List<Integer>> fourSum(int[] nums, long target) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length - 3; ) {for (int j = i + 1; j < nums.length - 2; ) {int left = j + 1, right = nums.length - 1;while (left < right) {if (nums[left] + nums[right] < target - nums[i] - nums[j]) {left++;} else if (nums[left] + nums[right] > target - nums[i] - nums[j]) {right--;} else {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[left]);list.add(nums[right]);ans.add(list);left++;right--;//双指针去重while (left < right && nums[left - 1] == nums[left]) {left++;}while (left < right && nums[right + 1] == nums[right]) {right--;}}}//第二个确定的数去重j++;while (j + 1 < nums.length - 1 && nums[j - 1] == nums[j]) {j++;}}//第一个确定的数去重i++;while (i + 1 < nums.length - 2 && nums[i - 1] == nums[i]) {i++;}}return ans;}
}
