1. 双指针算法
双指针算法是一种在数组或字符串中常用且高效的算法技术，它通过维护两个指针（或索引）来遍历数据结构，从而解决某些问题。这种算法能够减少不必要的重复遍历，降低时间复杂度，并且往往能够使得代码更加简洁易懂。
根据指针的的移动方向可以分为同向双指针，相向双指针，快慢指针
2. 同向双指针
2.1 移动零
思路：定义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 复写零
如果使用双指针从前往后进行维护，那么会把原来数组中的值覆盖掉，造成数据混乱，所以可以尝试采用从后往前覆盖的方法
思路：先找到最后一个复写的数，然后从后往前判断复写边界问题，如果最后一个复写的数为0，意味着 dest需要往后移动两位，此时就会造成越界修改，此时就需要进行判断，但不能通过 arr[cur]来判断，需要根据dest的位置来判读，因为arr[cur]为0时也存在两种情况：dest往后移动两位刚好等于数组长度或超出一个数组长度
class Solution { public void duplicateZeros(int[] arr) { //找到最后一个复写的0 int 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 快乐数
证明一定会出现循环：题中给出的数据范围是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 盛水最多的容器
如果直接进行暴力枚举出所有组合，那么一定会超时的，通过双指针可以对其进行优化
思路：先找一段区间进行分析，发现对于左右两端最小的数来说的话，继续向内模拟，无论是找到比这个数小的还是大的，都会使最终结果变小（找到小的数肯定会变小，找到大的数高度不变，宽度变小，最终还是变小），所以根据单调性，从整个区间开始，每次舍弃较小的，依次来得到不同的组合，最后比较结果最大的组合
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 有效三角形的个数
如果正常暴力枚举，三层循环的时间复杂度就太慢了
思路：
这里进行一个优化：先把数组排序，已经排好序的三个数中，较小的两个数之和大于最长的那条边，就可以判断为三角形还是通过双指针，从后往前，先确定一个最长的边，然后从剩下的区间中开始判断，由于已经排好序了，所以如果最小的那个数加起来就已经大于第三边，那么剩下的所有就都符合，同理，此时再把右指针左移，确定下一个区间
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 查找总价格为目标值的两个商品（两数之和）
也就是两数之和的问题，由于已经是排好顺序的数组，并且返回任意结果都行，通过使用双指针，如果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 三数之和
思路：先进行排序，然后确定一个数，剩下的两个数按照两数之和的方法解决
去重：由于已经排好顺序了，所以当找到一个符合条件的组合之后，左右两个指针之后代表的数之后的数如果相同，那么肯定就会重复，只需要把这些数跳过去，或者使用容器去重
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 四数之和
四数之和也就是在三数之和的基础上再确定一个数，需要注意的是，此时需要去重的点有：第一个确定的数和第二个确定的数，进行双指针算法时的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; } }
