双指针从零学习

双指针是算法中非常基础且重要的技巧，今天我来聊聊这个话题。

双指针，顾名思义就是使用两个指针来解决问题。这两个指针可以同向移动，也可以反向移动，甚至可以一个快一个慢。根据不同的场景，选择不同的指针策略，能够大大简化问题。

以一个常见问题为例：删除有序数组中的重复项。

解法一：暴力解法

最直观的想法是，遇到重复的就把后面的元素都前移一位。这样虽然能解决问题，但时间复杂度是O(n²)，空间复杂度是O(1)。

代码实现：

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;

    int len = nums.length;
    int i = 0;
    while (i < len) {
        if (i > 0 && nums[i] == nums[i-1]) {
            // 发现重复，将后面的元素前移
            for (int j = i; j < len - 1; j++) {
                nums[j] = nums[j+1];
            }
            len--; // 数组长度减一
        } else {
            i++; // 没有重复，继续检查下一个
        }
    }
    return len;
}

这种解法虽然直观，但效率不高，特别是当数组很大时。

解法二：双指针（快慢指针）

使用快慢指针是解决这类问题的经典方法。慢指针指向当前不重复序列的最后一个位置，快指针遍历数组。

代码实现：

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;

    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

这种方法时间复杂度是O(n)，空间复杂度是O(1)，非常高效。慢指针只有在遇到新元素时才移动，保证了数组的前slow+1个元素是不重复的。

解法三：双指针（计数法）

这种方法是对解法二的扩展，适用于"最多保留k个重复元素"的情况。这里我们以保留最多2个重复元素为例。

代码实现：

public int removeDuplicates(int[] nums) {
    if (nums.length <= 2) return nums.length;

    int index = 2;
    for (int i = 2; i < nums.length; i++) {
        if (nums[i] != nums[index-2]) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

这种方法的核心思想是，比较当前元素与应该保留的位置的前两个元素，如果不相同，则可以保留。

再来看另一个经典问题：三数之和。

解法一：暴力解法

最直观的想法是使用三重循环，找出所有和为0的三元组。

代码实现：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> triplet = new ArrayList<>();
                    triplet.add(nums[i]);
                    triplet.add(nums[j]);
                    triplet.add(nums[k]);
                    result.add(triplet);
                }
            }
        }
    }

    // 去重
    Set<List<Integer>> set = new HashSet<>(result);
    return new ArrayList<>(set);
}

这种解法时间复杂度是O(n³)，而且还需要额外的去重操作，效率极低。

解法二：排序+双指针

先对数组进行排序，然后固定一个数，使用双指针找出另外两个数，使三数之和为0。

代码实现：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    int n = nums.length;

    for (int i = 0; i < n - 2; i++) {
        // 跳过重复元素
        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) {
                result.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 result;
}

这种方法时间复杂度是O(n²)，空间复杂度是O(1)或O(n)（取决于排序算法的空间复杂度）。

解法三：哈希表+双指针

这种方法是解法二的变种，使用哈希表来存储已经遍历过的元素，但在这个问题中，由于需要去重，所以不如解法二高效。

代码实现：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    int n = nums.length;

    for (int i = 0; i < n - 2; i++) {
        // 跳过重复元素
        if (i > 0 && nums[i] == nums[i-1]) continue;

        Set<Integer> seen = new HashSet<>();
        for (int j = i + 1; j < n; j++) {
            int complement = -nums[i] - nums[j];
            if (seen.contains(complement)) {
                result.add(Arrays.asList(nums[i], nums[j], complement));
                // 跳过重复元素
                while (j < n - 1 && nums[j] == nums[j+1]) j++;
            }
            seen.add(nums[j]);
        }
    }

    return result;
}

这种方法时间复杂度也是O(n²)，但空间复杂度是O(n)，因为需要额外的哈希表。

双指针技巧在数组、链表等数据结构的问题中经常用到，掌握好这个技巧对解决算法问题非常有帮助。从上面的例子可以看出，双指针可以将时间复杂度从O(n²)降低到O(n)，或者从O(n³)降低到O(n²)，大大提高算法效率。