面试手撕算法高频专题：数组的双指针思想及应用（算法村第三关白银挑战）

所谓的双指针其实就是两个变量，不一定真的是指针。

1. 快慢指针：一起向前走
2. 对撞指针、相向指针：从两头向中间走
3. 背向指针：从中间向两头走

移除值为val的元素

题目描述

27. 移除元素 - 力扣（LeetCode）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

快慢指针

/**
 * @return 移除后val后数组的新长度
 */
public int removeElement(int[] nums, int val)
{
    int slow = 0;

    for (int fast = 0; fast < nums.length; fast++)
    {
        //nums[fast] == val时slow等待，直到下一个nums[fast]（!= val），然后将nums[slow]覆盖
        if (nums[fast] != val)
        {
            nums[slow] = nums[fast];
            slow++; //slow移动到下一个待写位置
        }
    }

    return slow;
}

上图的val=2

对撞指针+交换

/**
 * 核心思想：从右侧找到不是val的值来顶替左侧是val的值
 */
public int removeElement(int[] nums, int val)
{
    int left = 0;
    int right = nums.length - 1;

    while (left <= right)
    {
        if(nums[left] == val && nums[right] != val)
        {
            int temp = nums[left];
            nums[left] = nums[right];   //覆盖删除
            nums[right] = temp; //交换的目的是让right指针能够移动
        }

        //更新指针
        if (nums[left] != val)
            left++;
        if (nums[right] == val)
            right--;
    }

    return left;
}

对撞指针+覆盖

public int removeElement(int[] nums, int val)
{
    int left = 0;
    int right = nums.length - 1;

    while (left <= right)
    {
        if (nums[left] == val)
        {
            nums[left] = nums[right];
            right--;
        }
        else
            left++;
    }

    return right + 1;
}

删除有序数组中的重复项

题目描述

26. 删除有序数组中的重复项 - 力扣（LeetCode）

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

快慢指针

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

    for(int fast = 0; fast < nums.length; fast++)
    {
        //fast往下走，直到指向第一个与slow不同的元素
        if(nums[fast] != nums[slow])
        {
            slow++; //slow后移一位，存储新的不重复元素
            nums[slow] = nums[fast];
        }
    }

    return slow + 1;    //返回nums中唯一元素的个数。
}

进阶：重复元素保留k个

• 前 k 位直接保留
• **fast 不断向后遍历， nums[fast] 能够保留的前提是与nums[slow]**的前面第 k 个元素不同
• 保留后 slow 指向新的写入位置

public int removeDuplicates(int[] nums)
{
    int slow = 0;
    int k = 2;  //重复元素保留k个

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

    return slow;    //返回nums中唯一元素的个数。
}

按奇偶排序数组

题目描述

905. 按奇偶排序数组 - 力扣（LeetCode）

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入：nums = [0]
输出：[0]

对撞指针+交换

public int[] sortArrayByParity(int[] nums)
{
    int left = 0;
    int right = nums.length - 1;

    while (left < right)
    {
        //左奇右偶时两边交换，把奇数调到后面，偶数调到前面
        if(nums[left] % 2 == 1  && nums[right] % 2 == 0)
        {
            int t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
        }

        if(nums[left] % 2 == 0) left++; //跳过左边的偶数
        if(nums[right] % 2 == 1) right--; //跳过右边的奇数
    }

    return nums;
}

数组轮转

题目描述

189. 轮转数组 - 力扣（LeetCode）

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

三次翻转

public void rotate(int[] nums, int k)
{
    //举例nums:[1,2,3,4,5,6,7]
    k = k % nums.length;
	
    reverse(nums,0, nums.length - 1);	//nums:[7,6,5,4,3,2,1]
    reverse(nums,0,k-1);	//nums:[5,6,7,4,3,2,1]
    reverse(nums,k, nums.length - 1);	//nums:[5,6,7,1,2,3,4]
}

//反转指定区间
public void reverse(int[] nums, int left, int right)
{
    while (left < right)
    {
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;

        left++;
        right--;
    }
}

数组的区间专题

汇总区间

题目描述

228. 汇总区间 - 力扣（LeetCode）

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表* 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b" ，如果 a != b
• "a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

• 0 <= nums.length <= 20
• -231 <= nums[i] <= 231 - 1
• nums 中的所有值都 互不相同
• nums 按升序排列

解

1. slow 指向每个区间的起始位置， fast 从 slow 位置开始向后遍历，直到不满足连续递增或 fast 达到数组边界。当前区间结束
2. 将 slow 指向更新为 fast + 1，作为下一个区间的开始位置，fast继续向后遍历找下一个区间的结束位置，如此循环，直到 nums 遍历完毕

append(char c)：将指定的字符添加到当前StringBuilder对象的末尾。如果参数是数字，则自动转为字符

public List<String> summaryRanges(int[] nums)
{
    ArrayList<String> ans = new ArrayList<>();

    int slow = 0;
    int fast = 0;

    for (; fast < nums.length; fast++)
    {
        if(fast == nums.length - 1 || nums[fast]+1 != nums[fast + 1])
        {
            StringBuilder sb = new StringBuilder();
            sb.append(nums[slow]);

            if(nums[slow] != nums[fast])
                sb.append("->").append(nums[fast]);

            ans.add(sb.toString());

            slow = fast + 1;
        }
    }

    return ans;
}

缺失的区间

题目描述

163. 缺失的区间 - 力扣（LeetCode）

给你一个闭区间 [lower, upper] 和一个 按从小到大排序 的整数数组 nums ，其中元素的范围在闭区间 [lower, upper] 当中。

如果一个数字 x 在 [lower, upper] 区间内，并且 x 不在 nums 中，则认为 x 缺失。

返回 准确涵盖所有缺失数字 的 最小排序 区间列表。也就是说，nums 的任何元素都不在任何区间内，并且每个缺失的数字都在其中一个区间内。

示例 1：

输入: nums = [0, 1, 3, 50, 75], lower = 0 , upper = 99
输出: [[2,2],[4,49],[51,74],[76,99]]
解释：返回的区间是：
[2,2]
[4,49]
[51,74]
[76,99]

示例 2：

输入： nums = [-1], lower = -1, upper = -1
输出： []
解释： 没有缺失的区间，因为没有缺失的数字。

提示：

• -109 <= lower <= upper <= 109
• 0 <= nums.length <= 100
• lower <= nums[i] <= upper
• nums 中的所有值 互不相同

解

public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper)
{
    List<List<Integer>> missingRanges = new ArrayList<>();

    //[lower, upper]缺失
    if (nums.length == 0)
    {
        missingRanges.add(generateRange(lower, upper));
        return missingRanges;
    }

    //[lower, nums[0] - 1]缺失
    if (nums[0] > lower)
    {
        missingRanges.add(generateRange(lower, nums[0] - 1));
    }

    //i = 0起，[nums[i] + 1, nums[i + 1] - 1]缺失
    for (int i = 0; i < nums.length - 1; i++)
    {
        if(nums[i + 1] - nums[i] > 1)	//非连续递增
        {
            missingRanges.add(generateRange(nums[i] + 1, nums[i + 1] - 1));
        }
    }

    //[nums[length - 1] + 1, upper]缺失
    if (nums[nums.length - 1] < upper)
    {
        missingRanges.add(generateRange(nums[nums.length - 1] + 1, upper));
    }

    return missingRanges;	//返回所有缺失区间
}

//生成区间
public List<Integer> generateRange(int start, int end)
{
    ArrayList<Integer> range = new ArrayList<>();
    range.add(start);
    range.add(end);

    return range;
}

字符串替换空格

题目描述

（剑指offer）请实现一个函数，将一个字符串中的每个空格替换成**“%20”。例如，“We Are Happy.”** 经过替换之后为**“We%20Are%20Happy.”**

解

public class replaceSpaces
{
    public static void main(String[] args)
    {
        String str1 = replaceSpace_immutable("We Are Happy.");
        System.out.println(str1);    //We%20Are%20Happy.(正确)

        StringBuffer sb = new StringBuffer("We Are Happy.");
        String str2 = replaceSpace_variable(sb);
        System.out.println(str2);   //We%20Are%20Happy.(正确)

    }

    //存储字符串的空间不可变，或者存储空间不算大
    public static String replaceSpace_immutable(String str)
    {
        String res = "";

        for (int i = 0; i < str.length(); i++)
        {
            char c = str.charAt(i);

            if (c == ' ')
                res = res + "%20";
            else
                res = "%s%s".formatted(res, c); //效果相同
        }

        return res;
    }

    //存储字符串的空间可变，或者存储空间很大
    public static String replaceSpace_variable(StringBuffer str)
    {
        int blank = 0;  //str中的空格数
        //计算空格数
        for (int i = 0; i < str.length(); i++)
            if (str.charAt(i) == ' ')
                blank++;

        int fast = str.length() - 1;    //fast指向原长度的末尾

        //设置新的长度(StringBuffer才有的方法，String没有)
        str.setLength(str.length() + 2 * blank);

        int slow = str.length() - 1;    //slow指向新长度的末尾

        while (fast >=0 && fast < slow)
        {
            char c = str.charAt(fast);

            if (c == ' ')
            {
                str.setCharAt(slow,'0');	//复制
                slow--;
                str.setCharAt(slow,'2');
                slow--;
                str.setCharAt(slow,'%');
            }
            else
                str.setCharAt(slow, c);

            fast--;
            slow--;
        }

        return str.toString();
    }
}

replaceSpace_variable图解