双指针

10月 26 2022 学习>计算机科学 5 分钟读完 (约 797 字)

这个十月，我强迫自己每天做一道LeetCode。虽然中间有几天中断了，但最后还是完成了我的第一个“探索”单元。

对我来说，最有用的一课是一种叫做双指针的神奇技巧。起初我以为它是嵌套的两个for循环，但后来我发现它实际上更有意义，更有用。所以我想把它记录下来。

含义

同时使用两个指针来做迭代。

应用

当你想从两端向中间迭代数组时，你可以使用一个指针从头开始，而另一个指针从尾开始。它们有相同的步长。

// Reverse String

class Solution {
    public void reverseString(char[] s) {
        int i = 0;
        int j = s.length - 1;
        while (i < j) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
}

// Two Sum II - Input array is sorted
// 给出一个已经按非递减顺序排序的索引到1的整数数组，找出两个数字，使其相加等于一个特定的目标数

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int start = 0;
        int end = numbers.length - 1;
        while (start < end) {
            if (numbers[start] + numbers[end] == target) {
                break;
            } else if (numbers[start] + numbers[end] < target) {
                start ++;
            } else {
                end --;
            }
        }
        res[0] = start + 1;
        res[1] = end + 1;
        return res;
    }
}

当你想要一个慢速指针和一个快速指针时，你可以使用一个指针用于迭代，而另一个指针用于标记特殊位置。它们有不同的步长。

// Remove Element
// "i"用于迭代，"k"用于指示要移动的元素

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

这里还介绍了一个重要的概念：原地算法。

原地算法（in-place algorithm，也称“就地算法”）是基本上不需要借助额外的数据结构就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。¹

// Max Consecutive Ones
// "i"用于迭代，"max"用于找最大数

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (nums[i] == 0) {
                sum = 0;
            } else {
                max = Math.max(sum, max);
            }
        }
        return max;
    }
}

// Remove Duplicates from Sorted Array
// "i"用于迭代，"j"用于寻找特殊元素
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int j = 0;
        for (int i = 1; i < n; i++) {
            if (nums[j] != nums[i]) {
                j++;
                nums[j] = nums[i];  
            }  
        }
        return j + 1;
    }
}

// Move Zeroes
// "i"用于迭代，"k"用于指示非零元素

class Solution {
    public void moveZeroes(int[] nums) {  
        int n = nums.length;
        int k = 0;
        for (int i = 0; i < n; i++) {
            k = i;
            if (nums[i] == 0) {
                if (k < n-1) {
                    while (nums[k] == 0 && k < n-1) {k++; } 
                    int temp = nums[i];
                    nums[i] = nums[k];
                    nums[k] = temp;    
                } 
            }
        }  
    }
}