Leetcode Hot100 双指针

class Solution {
    public void moveZeroes(int[] nums) {
        int writePointer = 0; 
        for (int num:nums) { // 遍历数组中的每个元素
            if (num != 0) {
                nums[writePointer] = num; // 非0元素，直接写入数组更改
                writePointer++;
            }
        }
        for (int i = writePointer; i<nums.length; i++) {nums[i] = 0;} // 剩余位置全部填充0
       }
}

**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是数组的长度。遍历数组两次，第一次遍历非零元素，第二次填充零，总时间复杂度是 O(n)。
- **空间复杂度：O(1)**，只使用了常数级别的额外空间。

class Solution {
    public void moveZeroes(int[] nums) {
        // 初始化变量：数组长度、左指针（非零元素的边界）、右指针（遍历指针）
        int n = nums.length, left = 0, right = 0;

        // 遍历整个数组
        while (right < n) {
            // 如果当前元素不为零
            if (nums[right] != 0) {
                // 交换当前元素与左指针位置的元素
                swap(nums, left, right);
                // 左指针向右移动，标记非零元素的边界
                left++;
            }
            // 右指针继续向右移动
            right++;
        }
    }

    // 交换数组中两个位置的元素
    public void swap(int[] nums, int left, int right) {
        // 当 right 指针遇到非零元素时，将其与 left 指针位置的元素交换，并将 left 指针右移
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是数组的长度。整个过程中，left 和 right 指针最多各移动 n 次，因此总操作次数为 O(n)。
- **空间复杂度：O(1)**，只使用了常数级别的额外空间，没有使用额外的数据结构。

class Solution {
    public int maxArea(int[] height) {
        // 就是在 x距离最远的前提下，尽量选择最长的线
        // 以两边中的最短边和 i2 - i1 为底
        // 使用双指针移动，记录当前的最大容量，因为间隔是一致的1
        // 然后就保持长边不变，最短边移动，更新最大容量即可

        int left = 0; // 左指针从最左端开始
        int right = height.length - 1; // 右指针从最右端开始
        int maxArea = 0; // 记录最大容量

        while (left < right) {
            // 计算当前容量：较短边的高度 * 两指针之间的距离
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            // 更新最大容量
            maxArea = Math.max(maxArea, currentArea);

            // 移动较短的边，寻找更大的容量
            // 因为对于当前的容量，较短的边是限制容量的，所以移动较短的边可以尝试找到更大的容量
            if (height[left] < height[right]) {
                left++; // 左边较短，左指针右移
            } else {
                right--; // 右边较短，右指针左移
            }
        }

        return maxArea;
    }
}

---
双指针算法通过每次移动较短的边，确保了每一步都在寻找可能的更大容量，同时避免了不必要的计算。虽然看起来可能会错过某些组合，但实际上这些组合的容量一定小于或等于已经计算过的容量
---
**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是数组的长度。双指针从两端向中间移动，最多遍历数组一次。
- **空间复杂度：O(1)**，只使用了常数级别的额外空间。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        /*
        首先排序，降低重复数字造成的影响
            只有当值不同的时候才会进行枚举
        遍历数组，每次固定一个数
        跳指针，双指针，右指针左行
        */
        int n = nums.length; // 定义数组长度，后续要多次使用
        Arrays.sort(nums); // 排序
        List<List<Integer>> li = new ArrayList<List<Integer>>(); // 建立存储集合
        // 定义第一个数
        for (int i = 0; i < n; ++i) {
            // 需要和上一次枚举的数不相同
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 即：第一个数的下标不是0，且第一个数和第二个数相同的时候跳过判断
                // 因为这个情况在下标为0的时候已经枚举过了
                continue;
            }
            // 定义第三个数所对应的指针
            int right = n - 1; //初始指向数组的最右端

            // 定义第二个数
            for (int j = i + 1; j < n; ++j) {
                // 首先，定义第二个数的下标是在第一个数之后的
                // 如果第二个数和第一个数出现相同，说明这个情况在之前的枚举轮次已经枚举过了
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 需要保证 第二个数 的指针在 第三个数的 的指针的左侧
                // 即始终保持 a b c, a+b+c 的组合顺序
                while (j < right && nums[i] + nums[j] + nums[right] > 0) {
                    --right;
                }
                // 如果指针重合，随着 b 后续的增加,将不再有满足 a+b+c=0 ，a->b->c这个顺序的组合了，可以退出循环
                if (j == right) {
                    break;
                }
                if (nums[i] + nums[j] + nums[right] == 0) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[right]);
                    li.add(list);
                }
            }
        }
        return li;
    }
}