双指针

适用于数组划分的情况

数组划分：给一个标准或者制定一定规则，把数组划分为若干区间

LC283. 移动零

1. dest 与 cur 作用
   • dest: 零与非零元素的分割点，dest 所指向的是最后一个非零的下标
   • cur: 用来遍历数组
2. 先分为三个区间
   • [0, dest] 表示非零元素,
   • [dest + 1, cur - 1] 表示零元素,
   • [cur, n - 1] 表示未处理元素
3. 执行步骤：
   • 如果 nums[cur] 获取的变量是 0，那么执行 cur++
   • 如果 nums[cur] 获取的变量不是 0，那么先 dest++，然后交换 cur 与 dest 的下标，最后 cur++

输入数据：

步骤： 0 / 0

[0, dest]
已处理的非零元素

[dest + 1, cur - 1]
已处理的零元素

[cur, n - 1]
待处理未知元素

当前动作：等待输入...

public void moveZeroes(int[] nums) {
    // [0, dest] 非零元素, [dest + 1, cur - 1] 零元素, [cur, n - 1] 未处理元素
    int dest = -1, cur = 0;
    while (cur < nums.length) {
        if (nums[cur] != 0) {
            dest++;
            int tmp = nums[cur];
            nums[cur] = nums[dest];
            nums[dest] = tmp;
        } 
        cur++;
    }
}

LC1089. 复写零

思路：针对于数组排序先以异地的方式经行，如果成功了，那么就用就地的方式试试看

那么就用就地的方式不行，发现会覆盖其他元素，那么就以相反的方向试试看

异地

创建一个新的数组，按照题目要求， 如果是0，那么就复写两次，如果不是，那么就写一次即可（不提供代码了，就提供流程）

输入数据：

步骤： 0 / 0

原数组 (Source)只读，使用指针 i 进行遍历扫描

↓ 读写分离 ↓

新数组 (Destination)只写，使用指针 j 写入，长度必须与原数组一致

当前动作：等待输入...

就地

1. 通过 virtualLength 来获取到虚拟长度（就是 arr 更新之后的长度），通过它来判断是否最后一位是 0
   1. 如果是非零元素，那么 virtualLength 加 1
   2. 如果是元素为零，那么 virtualLength 加 2
2. 通过 virtualLength == arr.length + 1 判断是否过长
3. 最后利用双指针从后往前遍历覆盖

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public void duplicateZeros(int[] arr) {
  // 先计算出最后有效数据的最后一位
  int i = 0;
  int size = arr.length;
  int virtualLength = 0; // 虚拟长度（就是 arr 更新之后的长度）
  for (; virtualLength < size; i++) {
      if (arr[i] == 0) {
          // 元素是0的情况下，加两次
          virtualLength += 2;
      } else {
          virtualLength += 1;
      }
  }
  // 判断一下，最后一位的 0 有没有复写
  if (virtualLength == size + 1) {
      // 最后一位一定是 0
      arr[size - 1] = 0;
      size--;
      i--;
  }
  // 然后利用双指针从后往前遍历覆盖
  int right = size - 1, left = i - 1;
  while(left >= 0 && right > left) {
      if (arr[left] == 0) {
          // 先复写一次
          arr[right--] = arr[left];
      }
      // 正常覆盖
      arr[right--] = arr[left--];
  }
}

LC202. 快乐数

根据题意：它的结果要么是为 1，要么成环

下面的 执行一次 这个操作表示的是 将该数替换为它每个位置上的数字的平方和 这一个步骤

思路：

1. 把成为 1 的这个结果看为成为一个环，只不过这个环上的内容全是 1
2. 此时发现它们的结果都是成环，那么就可以想到 给定一个链表-判断链表中是否有环 这个题目
3. 用 slow 表示 执行一次的值，用 fast 表示 执行二次的值，终止条件为 slow 与 fast 是否相等，最后判断 slow 是否为 1 即可

为什么呢一定成环呢？可以通过 鸽巢原理 来解释

1. 查看输入参数的范围 $1<=n<=2^{3}1-1(2147483647)$
2. 那么它执行了一次后最大值为 $9^9\ast 10(810)$（把 $n$ 看为最大的 $9999999999$，执行一次后一定小于这个）
3. 获取到 “巢” 后，由于 $810<9999999999$ 所以区间 $[1,810]$ 里面的数执行一次后一定在这个区间里面
4. 由此可以得出，最多执行 $811$ 次后，里面的至少有一个数字会出现两次，即满足成环条件

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public boolean isHappy(int n) {
    int slow = func(n), fast = func(func(n));
    while(slow != fast) {
        slow = func(slow);
        fast = func(func(fast));
    }

    return slow == 1;
}

private int func(int n) {
    int ret = 0;
    while(n != 0) {
        int t = n % 10;
        ret = ret + t * t;
        n = n / 10;
    }

    return ret;
}

LC11. 盛最多水的容器

思路：

1. 先从两侧开始遍历，计算出体积

2. 算出面积后，把对应值较小的坐标往另一侧移动

   • 面积计算公式： $S=H\ast L$ 其中 $L_1=right-left$, $H_1=Min(height[left],height[right])$
   • 此时把值较小（高度较小）的一侧固定，只移动较大的一侧，发现 $L_2<L_1$
   • 又因为高度比较小，所以此时高度一定小于等于原来的高度，即：$H_1<=H_2$
   • 所以内部面积一定不会大于最外围的面积，那么就不需要管较小的一侧了，也就可以移动较小的一侧了

3. 反复循环，直到结束即可

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int maxArea(int[] height) {
    // 从两边开始
    int right = height.length - 1, left = 0;
    int max = -1;
    int tmp = 0;
    while (left < right) {
        max = (tmp = getMaxV(left, right, height)) > max ? tmp : max;
        // 只需要除去最小的一侧即可
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return max;
}

private int getMaxV(int left, int right, int[] array) {
    int minH = array[left] < array[right] ? array[left] : array[right];
    return (right - left) * minH;
}

LC611. 有效三角形的个数

思路：

1. 先对数组经行排序，把其变为一个有序数组

2. 固定最后一个值，它的下标为 beginIndex ，然后获取到左边区间的第一个值与最后一个值的下标 left, right

3. 判断这三个下标的值

   满足条件	额外意思	执行结果
   nums[left] + nums[right] > nums[beginIndex]	nums[right] 与 [left, right - 1] 这个区间内任何值组合都要大于 nums[beginIndex]	计算满足条件的个数，right--
   nums[left] + nums[right] <= nums[beginIndex]	nums[left] 与 [left + 1, right] 这个区间内任何值组合都要小于 nums[beginIndex]	left++

4. 最后重复上诉的操作即可

时间复杂度：$O(N^2)$ （排序 $N\times {\log }_{2}N$ + 遍历 $O(N^2)$）

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int triangleNumber(int[] nums) {
    // 先排序
    Arrays.sort(nums);
    int count = 0;
    
    // 从最后一个开始
    for(int beginIndex = nums.length - 1; beginIndex >= 2; beginIndex--) {
        int left = 0, right = beginIndex - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[beginIndex]) {
                // 说明值较大， nums[right] 与 [left, right - 1] 这个区间内任何值组合都要大于 nums[beginIndex]
                count += right - left;
                right--;
            } else {
                // 说明值较小， nums[left] 与 [left + 1, right] 这个区间内任何值组合都要小于 nums[beginIndex]
                left++;
            }
        }
    }
    return count;
}

LC15. 三数之和

思路：

1. 先排序，与上文中的 有效三角形的个数 这个有一举同工之妙

   原因：如果用暴力枚举，那么时间复杂度就是 $O(N^3)$ 那么就需要思考排序后的结果了，因为排序时间复杂度也就 $O(N\times {\log }_{2}N)$

2. 固定左侧，下标为 smallIndex ，然后把右侧看为一个有序数组，有效范围为 [left, right] ， 其中 left = smallIndex + 1, right = len - 1

3. 右侧的数组就可以结合 LCR 179. 查找总价格为目标值的两个商品 来做 只是需要把大小相等时候的逻辑修改为 添加符合条件的元素，左右两边各缩进一下，重新判断一下，防止漏元素

4. 重复上诉逻辑，最后需要考虑去重即可

去重细节：

1. 通过排序，可以把顺序不同但是结果相同的元素给去重了
2. 在获取到匹配的元素的时候，需要判断一下缩进后的边界元素的值是否与原来边界元素的值相等，如果相等那么就要持续缩进
3. 遍历完一次后，左侧固定位置往右边移动的时候需要判断一下原来固定的值是否与新固定的值一样，一样的话需要持续移动从而达到去重

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public List<List<Integer>> threeSum(int[] nums) {
    // 发现这个如果用暴力枚举，是三次，所以先排序
    Arrays.sort(nums);

    int n = nums.length;
    List<List<Integer>> list = new LinkedList<>();
    int sameV = -1;

    int smallIndex = 0;
    while (smallIndex < n - 2) {
        // 先固定一点
        int sV = nums[smallIndex];
        if (sV > 0) break; // 小优化
        // 获取到合法区间
        int left = smallIndex + 1, right = n - 1;
        while (left < right) {
            int sum = sV + nums[left] + nums[right];
            if (sum == 0) {
                list.add(new LinkedList<>(Arrays.asList(sV, nums[left], nums[right])));
                // 去重，排除相同的元素
                sameV = nums[left++];
                while (left < right && nums[left] == sameV) left++;
                sameV = nums[right--];
                while (left < right && nums[right] == sameV) right--;
            } else if (sum < 0) {
                // 太小，固定左边发现 右侧的值在 [left + 1, right] 这个区间内都不满足，所以要排除左侧
                left++;
            } else {
                // sum > 0
                right--;
            }
        }
        sameV = nums[smallIndex++];
        // 这个也是需要去重的
        while (smallIndex < n - 2 && sameV == nums[smallIndex]) {
            smallIndex++;
        }
    }

    return list;
}

LC18. 四数之和

思路与上面的三数之和很相似

1. 固定左边第一个数
2. 固定第二个数
3. 按照三数之和的思路遍历，注意去重即可

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public List<List<Integer>> fourSum(int[] nums, int target) {
    // 先排序
    Arrays.sort(nums);

    // 必须用 long 不然int会溢出
    long tar = (long)target;
    // 与三数之和差不多
    int n = nums.length;
    List<List<Integer>> ret = new LinkedList<>();
    for (int i = 0; i < n - 3; ) {
        int iV = nums[i];
        for (int j = i + 1; j < n - 2;) {
            int jV = nums[j];
            int left = j + 1, right = n - 1;
            while (left < right) {
                long sum = (long)iV + (long)jV + (long)nums[left] + (long)nums[right];
                if (sum == tar) {
                    // 相等
                    ret.add(Arrays.asList(iV, jV, nums[left], nums[right]));
                    // 必须是 left++ 在前面
                    while (left < right && nums[left++] == nums[left]);
                    while (left < right && nums[right--] == nums[right]);
                } else if (sum < tar) {
                    left++;
                } else {
                    // 不相等
                    right--;
                }
            }

            // 一次循环完毕
            while (j < n - 2 && nums[j++] == nums[j]);
        }
        while (i < n - 3 && nums[i++] == nums[i]);
    }

    return ret;
}