算法【Java】—— 双指针算法

双指针算法，通常用于在数组或链表等数据结构中快速找到特定的解决方案。双指针算法的核心是使用两个指针在数组或链表中遍历数据结构，以解决问题，如求两数之和、找环开始节点、求链表的中点等。

以下是一些常见的双指针算法的例子：

1. 求两数之和：给定一个整数数组 nums 和一个目标值 target，请你在数组中找出和为目标值的那两个整数，并返回他们的数组下标。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    return new int[0];  // 无解的情况
}

2. 移除元素：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要 使用额外的数组空间，你 必须 仅使用 O(1) 额外空间并 原地 修改输入数组。

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

3. 快乐数：编写一个函数来检测一个数是否是快乐数。

public boolean isHappy(int n) {
    int slow = n;
    int fast = getNextNumber(n);
 
    while (slow != fast && fast != 1) {
        slow = getNextNumber(slow);
        fast = getNextNumber(getNextNumber(fast));
    }
 
    return fast == 1;
}
 
public int getNextNumber(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

以上例子展示了双指针算法在求解特定问题中的应用，具有很好的教育意义和实用价值。