【面试算法笔记】0103-数组-双指针2

面试算法笔记2026年4月·算法LeetCode
zbhgis 浩瀚地学511 字3 分钟
创建于 更新于

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

力扣88. 合并两个有序数组

链接：https://leetcode.cn/problems/merge-sorted-array/description/

注意点

倒序双指针做法。

这道题的题目关键在于答案怎么放入。

1.设计三个指针，分别直接指向nums1, nums2, nums的末尾。

2.当num2的指针没有指向0的时候，即nums2中的元素还没合并完的时候，分为两种情况，一种是nums1[len1]的值大于等于nums2[len2]，这个时候就需要将nums1[len]赋值为nums1[len1]，把nums1的元素插入到对应的位置，同时len和len1同时往前移动一格；反之同理。

3.这道题如果从前面插入元素的话，那么如果遇到先将nums2的元素插入到nums1中，就会出现覆盖的情况，因此不建议这么做。那为啥可以从后面插入元素呢，因为这道题目输入的nums1已经为m+n长度的。

代码

Java
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while (len2 >= 0) {
            if (len1 >= 0 && nums1[len1] >= nums2[len2]) {
                nums1[len --] = nums1[len1 --];
            } else {
                nums1[len --] = nums2[len2 --];
            }
        }
    }
}

时空复杂度分析

单层循环，会碰到len2和len1长度的数组都遍历的情况。所以时间复杂度为O(m+n)

空间复杂度为O(1)

洛谷T227292 【排序】合并两个有序数组

链接：https://www.luogu.com.cn/problem/T227292#ide

注意点

同上

代码

Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mx = 1000001;
        int[] nums1 = new int[mx];
        for (int i = 0; i < n; i ++) {
            nums1[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] nums2 = new int[mx];
        for (int i = 0; i < m; i ++) {
            nums2[i] = sc.nextInt();
        }
        int len1 = n - 1;
        int len2 = m - 1;
        int len = n + m - 1;
        while (len2 >= 0) {
            if (len1 >= 0 && nums1[len1] >= nums2[len2]) nums1[len --] = nums1[len1 --];
            else nums1[len --] = nums2[len2 --];
        }
        for (int i = 0; i <= n + m - 1; i ++) {
            System.out.print(nums1[i] + " "); 
        }
    }
}

时空复杂度分析

同上

力扣977. 有序数组的平方

链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

注意点

相向指针做法。

这道题的题目关键在于将计算后的平方结果有序放入。

1.设计两个指针，一头一尾。

2.核心逻辑就是，计算完平方之后，遍历原始位置，把大的数从后往前放入数组中即可。

代码

Java
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int i = 0;
        int j = n - 1;
        for (int p = n - 1; p >= 0; p --) {
            int x = nums[i] * nums[i];
            int y = nums[j] * nums[j];
            if (x > y) {
                ans[p] = x;
                i ++;
            } else {
                ans[p] = y;
                j --;
            }
        }
        return ans;
    }
}

时空复杂度分析

单层循环，需要遍历n次，因此时间复杂度为O(n)

空间复杂度为O(1)

参考

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html