双指针

双指针技巧

对撞指针

// 两数之和II（LeetCode 167）
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[0];
}

快慢指针

// 环形链表（LeetCode 141）
public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            return true;
        }
    }
    return false;
}

同向双指针

// 删除排序数组中的重复项（LeetCode 26）
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;
}

LeetCode题目

移动零（LeetCode 283）

public void moveZeroes(int[] nums) {
    int slow = 0;

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

    while (slow < nums.length) {
        nums[slow++] = 0;
    }
}

反转字符串中的元音字母（LeetCode 345）

public String reverseVowels(String s) {
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    String vowels = "aeiouAEIOU";

    while (left < right) {
        while (left < right && vowels.indexOf(chars[left]) == -1) {
            left++;
        }
        while (left < right && vowels.indexOf(chars[right]) == -1) {
            right--;
        }

        if (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
    return new String(chars);
}

接雨水（LeetCode 42）

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int result = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                result += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                result += rightMax - height[right];
            }
            right--;
        }
    }
    return result;
}

练习题

1. 验证回文串（LeetCode 125）
2. 长度最小的子数组（LeetCode 209）
3. 环形链表II（LeetCode 142）