04 数组

发表于 2015/02/23 更新于 2025/02/02

作者 Hacket Zeng

96 分钟阅读

04 数组

数组快慢指针/双指针相关题

26. 删除有序数组中的重复项(保留一个) easy 快慢指针

题目

解法 1：暴力 TreeSet

  
public static int removeDuplicates1(int[] nums) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
        nums[i] = 0;
    }
    Iterator<Integer> iterator = set.iterator();
    int i = 0;
    while (iterator.hasNext()) {
        nums[i] = iterator.next();
        i++;
    }
    return i;
}

解法 2：双指针

思路

首先注意数组是有序的，那么重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。
考虑用 2 个指针，一个在前记作 p，一个在后记作 q
如果 p 和 q 位置相等时，q++ 移动，p 不动；不相等将 q 移动到 p+1 位置，p++ 往前移动，q++ 往前移动
当 q>=数组长度时，遍历结束，返回 p+1（题目要求不是 0 开始）

代码

  
public static int removeDuplicates(int[] nums) {
    // 边界
    if (nums.length <= 1) return nums.length;
    int p = 0;
    int q = p + 1;
    while (q < nums.length) {
        if (nums[q] != nums[p]) {
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1;
}

复杂度

时间复杂度 O(n)
空间复杂度 O(1)

解法 3：解法 2 优化版最优解

考虑如下数组：

此时数组中没有重复元素，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。

  
public static int removeDuplicates(int[] nums) {
    // 边界
    if (nums.length <= 1) return nums.length;
    int p = 0;
    int q = p + 1;
    while (q < nums.length) {
        if (nums[q] != nums[p]) {
            if (q - p > 1) { // 避免连续不是重复的元素不必要的赋值
                nums[p + 1] = nums[q];
            }
            p++;
        }
        q++;
    }
    return p + 1;
}

27. 移除元素（不保留元素，对顺序无要求）easy 快慢指针

题目

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解法 1：双指针

思路

双指针 slow 和 fast；slow 用于将不等于 val 的替换到该位置的指针，每替换一个值就 +1，fast 用于寻找不等于 val 的指针
每当 fast 寻找到一个不等于 val 的值，就将该值替换到 slow 位置上去，slow++
当 fast 超过数组长度，也就将所有不等于 val 的值都摞动到了前面
返回 slow 即可

代码

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

解法 2：双指针优化版本最优解

双指针优化版本
如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val=1 时，我们需要把每一个元素都左移一位。实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。
思路

还是双指针 left 和 right
当 left 等于 val 时，从最后取一个元素来替换到 left，right–
如果 left 不等于 0，left++
直到 left>right

  
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 left;
}

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与解法一不同的是，解法二避免了需要保留的元素的重复赋值操作。
和 26 题删除有序数组中的重复项：

26 题删除有序数组中的重复项会保留重复元素中的一个，而 27 题的移除元素会把相同的元素都移除掉
26 题的指针 pq 位置的值进行对比，不相等时会把 q 的值覆盖到 p+1 位置，p 和 q 都 ++（把前面的元素确定好，）
27 题的指针是 q 位置的值和 val 进行对比，不相等时会把 q 的值覆盖到 p 位置，p 和 q 都 ++(相当于每找到一个不等于 val 的值将其移动到前面来)
这 2 题有点类似

283. 移动零(不保留元素，对顺序有要求) easy

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

解法 1：快慢指针，两次遍历

思路

快慢指针 slow，fast；思路同移除元素，只是在这个基础上找到 slow
不等于 0 的元素都移动到 [0, slow)，后面的元素再来一次遍历将其置为 0 即可

代码

  
public static void moveZeroes(int[] nums) {
    if (nums == null || nums.length <= 1) return;
    int slow = 0;
    int fast = 0; // 不能从1开始，否则索引为0处的就会被忽略
    // 先将不是0的元素移动到最前面
    while (fast < nums.length) {
        if (nums[fast] != 0) { // 找到不等于0的就摞动到前面来
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    // 再将后面的元素置为0
    for (int i = slow; i < nums.length; i++) {
        nums[i] = 0;
    }
}

解法 2：类快速排序 partition，一次遍历

思路

参考快速排序选择完基准值后的排序操作 (其实就是 partition)，这里基准值为 0，把不等于 0 的放在左边，等于 0 的放到右边

代码 1

  
public static void moveZeroes1(int[] nums) {
    if (nums == null || nums.length <= 1) return;
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            // 交换
            // swap(nums, fast, slow);
            // 可以直接不用交换，把fast赋值给slow，fast处置为0即可
            nums[slow] = nums[fast];
            nums[fast] = 0;
            slow++;
        }
    }
}
private static void swap(int[] nums, int m, int n) {
    int temp = nums[m];
    nums[m] = nums[n];
    nums[n] = temp;
}

代码 1 不足：存在重复的交换，slow=fast=0，都不等于 0 时，slow 和 fast 还要进行一次多余的交换操作

代码 2 最优解

对解代码 1 的优化，它避免了数组开头是非零元素的交换也就是阻止（i==j）时交换。当 i > j 时，只需要把 i 的值赋值给 j 并把原位置的值置 0。同时这里也把交换操作换成了赋值操作，减少了一条操作语句，理论上能更节省时间

  
public static void moveZeroes(int[] nums) {
    if (nums == null) return;
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            if (fast > slow) {
                nums[slow] = nums[fast];
                nums[fast] = 0;
            }
            slow++;
        }
    }
}

前缀和

303. 区域和检索 - 数组不可变一维数组前缀和 easy

题目

给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

解法 1：暴力

  
class NumArray {
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    public int sumRange(int left, int right) {
        int res = 0;
        for (int i = left; i <= right; i++) {
            res += nums[i];
        }
        return res;
    }
}

每次调用 sumRange 都需要重新计算 [left, right] 之间的和，效率比较低下，时间复杂度为 O(n)

解法 2：前缀和

前缀和可将时间复杂度降低到 O(1)
思路 1：

数组 preSum，每个位置 i 保存前 i 位置的和
现在要计算 [left, right] 之间的和，其实就是第 right 位置之前的和 - 第 left-1 位置之前的和为所求（需要处理 left=0 的特殊情况），即 preSum[right] - preSum[left-1]

  
public class NumArray {
    private int[] preSum;
    public NumArray(int[] nums) {
        if (nums.length <= 0) return;
        preSum = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
    }
    public int sumRange(int left, int right) {
        if (left == 0) {
            return preSum[right];
        }
        return preSum[right] - preSum[left - 1];
    }
}

思路 2 最优解（预留 nums[0] 位置）

思路 1 中第 i 位置保存的是前 i 位置所有的和，包括第 i 位置，所以在计算 [left, right] 的和的时候需要 right-(left-1)，需要处理 left=0 的情况
那么我们换种思路，preSum[0] 固定为 0，preSum[i] 的位置保存前 i-1 位置所有元素的和；总共需要 nums.length+1 的位置
在获取 [left, right] 之间和的时候，只需要返回 preSum[right+1] - preSum[left] 即可，不用处理 left=0 的情况。

  
public class NumArray2 {
    private int[] preSum;
    public NumArray2(int[] nums) {
        if (nums.length <= 0) return;
        preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

304. 二维区域和检索 - 矩阵不可变

题目

给定一个二维矩阵 matrix，以下类型的多个请求：计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)

解法 1：二维前缀和

思路

preSum[][] 是一个二维数组，预留 preSum[row][0] 和 preSum[0][col]，方便计算 row=0 和 col=0 的情况；preSum[i][j] 存放的是矩阵左上角原点 [0,0] 到 [i-1][j-1] 所有元素之和
首先需要将 matrix 计算二维前缀和存储到 preSum 二维数组中去，其实就是计算几块区域之和
1. 计算 preSum[i][j]，其实就是其左边的矩阵 + 上边的矩阵之和，因为多减去了一个角 matrix[i-1][j-1]，所以需要加上
2. preSum[i][j] 计算=preSum[i][j-1]+preSum[i-1][j]-maxtrix[i-1][j-1]
sumRegion 计算子矩阵之和
1. S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G) // S(O,G) 被多减去了一次，需要加回来

代码

  
class NumMatrix {
    private int[][] preMatrixSum;
    public NumMatrix(int[][] matrix) {
        preMatrixSum = new int[matrix.length + 1][matrix[0].length + 1];
//        preMatrixSum[i][j]存储的是[0][0]-[i-1][j-1]所有元素的和
        for (int row = 1; row < preMatrixSum.length; row++) {
            for (int column = 1; column < preMatrixSum[row].length; column++) {
                preMatrixSum[row][column] = preMatrixSum[row - 1][column] + preMatrixSum[row][column - 1] + matrix[row - 1][column - 1] - preMatrixSum[row - 1][column - 1];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preMatrixSum[row2 + 1][col2 + 1] - preMatrixSum[row1][col2+1] - preMatrixSum[row2 + 1][col1] + preMatrixSum[row1][col1];
    }
}

滑动窗口相关题

nSum 问题

一个方法团灭 NSUM 问题

两数之和

无重复值的无序数组，返回索引时间 O(n) 空间 O(n)

  
public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int val = target - nums[i];
        if (map.containsKey(val) && map.get(val) != i) {
            int index = map.get(val);
            return new int[]{index, i};
        } else {
            map.put(nums[i], i);
        }
    }
    return new int[0];
}

无重复值的升序数组时间 O(n) 空间 O(1)

  
public static int[] twoSum1(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) { // 相当于代表只有单个元素了，不需要考虑
        int res = nums[left] + nums[right];
        if (res == target) {
            return new int[]{left + 1, right + 1}; // 索引从1开始
        } else if (res > target) {
            right--;
        } else {
            left++;
        }
    }
    return new int[0];
}

有重复值的无序数组，返回元素

  
public static List<List<Integer>> twoSum(int[] nums, int target) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int leftVal = nums[left];
        int rightVal = nums[right];
        int r = leftVal + rightVal;
        if (r == target) {
            List<Integer> tuple = new ArrayList<>();
            tuple.add(leftVal);
            tuple.add(rightVal);
            res.add(tuple);
            while (left < right && nums[right] == rightVal) {
                right--;
            }
            while (left < right && nums[left] == leftVal) {
                left++;
            }
        } else if (r > target) {
            while (left < right && nums[right] == rightVal) {
                right--;
            }
        } else {
            while (left < right && nums[left] == leftVal) {
                left++;
            }
        }
    }
    return res;
}

两数之和等于 target（有无重复元素都行）easy

1. 两数之和(有无重复值、无序数组、返回索引)

解法 1：先排序后二分法 (双指针)
解法 2：哈希表

  
public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int val = target - nums[i];
        if (map.containsKey(val) && map.get(val) != i) {
            int index = map.get(val);
            return new int[]{index, i};
        } else {
            map.put(nums[i], i);
        }
    }
    return new int[0];
}

167. 两数之和 II - 输入有序数组（有序，返回索引）

题目

给你一个下标从 1 开始的整数数组 numbers ，该数组已按**_ _ 非递减顺序排列 **，请你从数组中找出满足相加之和等于目标数 target 的两个数。输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

  
public static int[] twoSum1(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) { // 相当于代表只有单个元素了，不需要考虑
        int res = nums[left] + nums[right];
        if (res == target) {
            return new int[]{left + 1, right + 1}; // 索引从1开始
        } else if (res > target) {
            right--;
        } else {
            left++;
        }
    }
    return new int[0];
}

剑指 Offer 57. 和为s的两个数字（有序，返回元素）

题目

输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。 输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]

解法 1：哈希表

思路

用哈希表 HashMap 或 HashSet:
key 存数组的值，value 存数组的索引
每次遍历时，需要找到 target-nums[i] 的值，从哈希表中去找，是否存在该值
1. 如果存在，直接返回该值
2. 如果不存在，将其存到哈希表中去

  
public static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int val = target - nums[i];
        if (map.containsKey(val)) {
            return new int[]{nums[i], val};
        } else {
            map.put(nums[i], i);
        }
    }
    return null;
}

解法 2：双指针最优解

nums 是排序数组，因此可使用双指针法将空间复杂度降低至 O(1)

  
public static int[] twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) { // 不需要考虑相等的情况
        int s = nums[left] + nums[right];
        if (s == target) {
            return new int[]{nums[left], nums[right]};
        } else if (s > target) {
            // 继续往左，缩小右边
            right--;
        } else { // mid < target
            left++;
        }
    }
    return null;
}

两数之和变种

两数之和等于 target 的不重复组合数目（存在重复数） medium

题目

给出未排序数组 nums 和指定目标 target，nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。

思路

数组先按升序排好序
双指针 left 和 right 查找
1. 二分搜索找到等于 target 的两个数
2. 由于存在了重复数，所以 left 需要往右 left++，right 需要往左 right–，找到一个不是重复的数（保证重复的答案只会被添加 1 次）

代码

  
public static int twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) return 0;
    // 数组必须有序
    Arrays.sort(nums);
    // 如果题目要求输出的是数量，用count就行，不需要用map
    // int count = 0;
    // 如果题目要求输出的是不重复的值，用Map
    Map<Integer, Integer> map = new HashMap<>();
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int leftVal = nums[left];
        int rightVal = nums[right];
        int val = leftVal + rightVal;
        if (val > target) {
            while (left < right && nums[right] == rightVal) {
                right--;
            }
        } else if (val < target) {
            while (left < right && nums[left] == leftVal) {
                left++;
            }
        } else {
            // 相等
            map.put(leftVal, rightVal);
            // 下面这样会导致重复元素被添加
            // left++;
            //  right--;
            // 跳过所有重复的元素
            while (left < right && nums[right] == rightVal) {
                right--;
            }
            while (left < right && nums[left] == leftVal) {
                left++;
            }
        }
    }
    return map.size();
}

时间复杂度：排序 O(nlogn)，遍历为 O(n)，整体为 O(nlogn)

三数之和

15. 三数之和 medium

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。

解法 1：排序、对每个元素求两数之和、去重

思路

可以把问题转换为遍历数组 nums，从第 0 个元素开始，一个个来求带重复元素的两数之和
先对数组进行升序排序
求解第 i=0 个元素的三数之和
1. 转换为求解 target-nums[i] 的两数之和，数组 nums[i+1, n-1]
2. 然后将求解的两数之和加上当前 nums[i] 即是三数之和
一轮遍历后，需要注意重复元素，要跳过前后数组元素相同的，否则会出现重复的结果
求解完一个元素后，数组缩小

代码

  
public static List<List<Integer>> threeSum(int[] nums, int target) {
    // 先排序
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    // 穷举 threeSum 的第一个数
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        // 找两个之和为nums[i]
        List<List<Integer>> tuples = twoSum(nums, i + 1, target - num);
        // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
        for (List<Integer> tuple : tuples) {
            tuple.add(num);
            res.add(tuple);
        }
        // 跳过第一个数字重复的情况，否则会出现重复结果
        while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
            i++;
        }
    }
    return res;
}
// 有重复数的两数之和
public static List<List<Integer>> twoSum(int[] nums, int start, int target) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    int left = start;
    int right = nums.length - 1;
    while (left < right) {
        int leftVal = nums[left];
        int rightVal = nums[right];
        int r = leftVal + rightVal;
        if (r == target) {
            List<Integer> tuple = new ArrayList<>();
            tuple.add(leftVal);
            tuple.add(rightVal);
            res.add(tuple);
            while (left < right && nums[right] == rightVal) {
                right--;
            }
            while (left < right && nums[left] == leftVal) {
                left++;
            }
        } else if (r > target) {
            while (left < right && nums[right] == rightVal) {
                right--;
            }
        } else {
            while (left < right && nums[left] == leftVal) {
                left++;
            }
        }
    }
    return res;
}

解法 2：排序 + 双指针对解法 1 的条件增强（最右解）

题目关键是去重
思路

边界判断，数组为 null 或数组长度小于 3，返回 []
对数组进行排序
遍历排序后的数组
1. 若 nums[i]>0，因为已排好序，所以后面的三个数相加之和，不可能等于 0，直接返回结果
2. 遍历过程中重复的元素，跳过，避免出现重复解
3. 双指针求解有重复元素的两数之和，左指针 left=i+1，右指针 right=n-1，循环条件 while(left<right)
  1. nums[i]+nums[left]+nums[right]=0 时，将该三个元素加入到结果中；去重 left 右边的元素，去重 right 左边的元素，来求解新的解
  2. 若 nums[i]+nums[left]+nums[right]>0 时，nums[right] 过大，左移，right–
  3. 若 nums[i]+nums[left]+nums[right]<0 时，nums[left] 过小，右移，left++

注意：nums[i] > target 返回结果，如果存在负数这个条件要去掉，否则失败

代码

  
public static List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    // 边界
    if (nums == null || nums.length < 3) return res;
    // 排序
    Arrays.sort(nums);

    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // 大于target，就不可能还能找到3个数等于target，直接返回结果，如果target不为负数这个条件就不要加
        if (nums[i]>0 && nums[i] > target) {
            return res;
        }
        // 出现重复的元素，直接跳过到下一个元素，对于需要求四数之和，如果是这种[0,1,1,1,1]就过滤掉了
//            if (i > 0 && nums[i] == nums[i - 1]) {
//                continue;
//            }
        // 有重复元素的两数之和求解
        int cur = nums[i];
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int leftVal = nums[left];
            int rightVal = nums[right];
            int tmp = leftVal + rightVal + cur;
            if (tmp == target) {
                List<Integer> triple = new ArrayList<>();
                triple.add(cur);
                triple.add(nums[left]);
                triple.add(nums[right]);
                res.add(triple);
                while (left < right && nums[left] == leftVal) {
                    left++;
                }
                while (left < right && nums[right] == rightVal) {
                    right--;
                }
            } else if (tmp > target) {
                right--;
            } else {
                left++;
            }
        }
        // 过滤掉前后元素重复的
        while (i < n - 1 && nums[i] == nums[i + 1]) {
            i++;
        }
    }
    return res;
}

*复杂度

时间复杂度 O(n^2)，数组排序 O(nlogn)，遍历数组 O(n)，双指针遍历 O(n)，整体 O(n^2)
空间复杂度 O(1)

16. 最接近的三数之和 medium

题目

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

解法 1：排序 + 双指针

思路

先升序排序
临时变量dx记录当前三数之和 -target 的差值
遍历数组，对每个数找两数之和
1. 双指针 left、right
2. 如果找到了等于 target 的三数之和，直接返回
3. 如果三数之和大于 target，right–；比较当前三数之和 -target 和 dx 绝对值比较，小的赋值为 dx
4. 如果三数之和小于 target，left++；比较当前三数之和 -target 和 dx 绝对值比较，小的赋值为 dx
返回 dx+target

代码

  
public static int threeSumClosest1(int[] nums, int target) {
    // 排序
    Arrays.sort(nums);

    int n = nums.length;
    int dx = Integer.MAX_VALUE; // 和目前和-target的结果
    for (int i = 0; i < n; i++) {
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int val = nums[left] + nums[right];
            if (val == target - nums[i]) {
                dx = 0;
                return dx + target;
            }
            // 计算
            int tempDx = nums[left] + nums[right] + nums[i] - target;
            if (Math.abs(tempDx) < Math.abs(dx)) {
                dx = tempDx;
            }
            if (val > target - nums[i]) {
                right--;
            } else {
                left++;
            }
        }
    }
    return dx + target;
}

时间复杂度：O(n^2) 排序 O(nlogn)，两层循环

四数之和

18. 四数之和 medium

思路

先排序
对每个元素寻找三数之和
过滤重复元素

代码

  
public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    // 排序
    Arrays.sort(nums);
    // 求解每个元素的三数之和
    for (int i = 0; i < nums.length; i++) {
        // 求解每个元素的三数之和
        List<List<Integer>> tripleList = threeSum(nums, i + 1, target - nums[i]);
        // 为每个符合条件的三数之和增加nums[i]元素组成四数之和
        for (List<Integer> list : tripleList) {
            list.add(nums[i]);
            res.add(list);
        }
        // 过滤掉前后元素重复的
        while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
            i++;
        }
    }
    return res;
}

private static List<List<Integer>> threeSum(int[] nums, int start, int target) {
    List<List<Integer>> res = new ArrayList<>();
    // 边界
    if (nums == null) {
        return res;
    }
    int n = nums.length;
    if (n - start < 2) {
        return res;
    }
    // 求解每个元素的两数之和(带重复数)
    for (int i = start; i < n; i++) {

        // 提前剪枝，可防止
        if (nums[i] > 0 && nums[i] > target) {
            return res;
        }

        // 不能将判断重复的条件写在这里 如果是这种[0,1,1,1,1]就过滤掉了
//            if (i > 0 && nums[i] == nums[i - 1]) {
//                continue;
//            }

        int cur = nums[i];
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int leftVal = nums[left];
            int rightVal = nums[right];
            // 直接相加会溢出
            int tmp = leftVal + rightVal + cur;
            if (tmp == target) {
                List<Integer> tripleList = new ArrayList<>();
                tripleList.add(nums[i]);
                tripleList.add(leftVal);
                tripleList.add(rightVal);
                res.add(tripleList);
                // 去除重复解
                while (left < right && nums[left] == leftVal) {
                    left++;
                }
                while (left < right && nums[right] == rightVal) {
                    right--;
                }
            } else if (tmp > target) {
                right--;
            } else {
                left++;
            }
        }
        // 过滤掉前后元素重复的
        while (i < n - 1 && nums[i] == nums[i + 1]) {
            i++;
        }
    }
    return res;
}

注意

过滤重复元素，不能提前过滤，否则 [0,1,1,1,1] 这种测试 case 就过不了

  
// 过滤掉前后元素重复的
// 不能将判断重复的条件写在这里 如果是这种[0,1,1,1,1]就过滤掉了
//            if (i > 0 && nums[i] == nums[i - 1]) {
//                continue;
//            }

// ... 寻找三数之和？
// 这种就可以
while (i < n - 1 && nums[i] == nums[i + 1]) {
    i++;
}

target 等于负数时剪枝要判断 nums[i] 大于 0

  
if (nums[i] > 0 && nums[i] > target) {
    return res;
}

要注意 target 溢出了，提前剪枝就好了

因为官方增加了一个新的用例 {1000000000，1000000000，1000000000，1000000000} 0 导致了代码出现溢出错误，是因为 int 的只能到表示 [-2147483648,2147483647]，所以在判断 num[a]+num[b]+num[c]+num[d]<target 时会溢出。因为不想对代码进行大改了所以将表达式调整为 nums[a]+nums[b]-target<-(nums[c]+nums[d]) 这样子就不会溢出了。当然也可以使用 long long int 来表示数值，这样也不会溢出。(边界处理很重要，但学习双指针的思想更重要~)

nSum n 数之和

思路

我们求解四数之和时，对每个元素求解三数之和，并去重；三数之和是对每个元素求两数之和；
其实这就是一个递归过程

代码

  
public static List<List<Integer>> nSum(int[] nums, int n, int target) {
    Arrays.sort(nums);
    return nSum(nums, n, 0, target);
}

public static List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
    List<List<Integer>> res = new ArrayList<>();
    int size = nums.length;
    // 至少是两数之和且start超过了数组大小
    if (n < 2 || size < start) return res;
    if (n == 2) { // 两数之和重复数版
        int left = start;
        int right = size - 1;
        while (left < right) {
            int leftVal = nums[left];
            int rightVal = nums[right];
            int val = leftVal + rightVal;
            if (val == target) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(leftVal);
                tmp.add(rightVal);
                res.add(tmp);
                // 去除重复值
                while (left < right && nums[left] == leftVal) {
                    left++;
                }
                while (left < right && nums[right] == rightVal) {
                    right--;
                }
            } else if (val > target) {
                right--;
            } else {
                left++;
            }
        }
    } else {
        // n > 2 时，递归计算 (n-1)Sum 的结果
        for (int i = start; i < size; i++) {
            // 大于target，就不可能还能找到3个数等于target，直接返回结果，如果target不为负数这个条件就不要加
            if (nums[i] > 0 && nums[i] > target) {
                return res;
            }
            List<List<Integer>> tmp = nSum(nums, n - 1, i + 1, target - nums[i]);
            for (List<Integer> list : tmp) {
                // (n-1)Sum 加上 nums[i] 就是 nSum
                list.add(nums[i]);
                res.add(list);
            }
            // 去除重复
            while (i < n - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
    }
    return res;
}

矩阵 (二维数组) 题

矩阵旋转相关

48. 旋转图像 medium

题目

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

解法 1：临时矩阵

思路

对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。因此对于矩阵中的元素 matrix[row][col] 在旋转后，它的新位置为 matrix[col][n-row-1]
用一个临时的矩阵 temp 来存储转换后的元素
最后将 temp 中的元素再赋值给 matrix，即可完成转换

代码

  
// 临时矩阵
public static void rotate(int[][] matrix) { // n=4
    int n = matrix.length;
    // 新建一个临时矩阵，存储翻转后的结果
    // matrix[i][j]翻转90°后的位置变成matrix[j][n-i-1]
    // matrix[0][0] 翻转90° 在matrix[0][4-0-1]即matrix[0][3]位置
    int[][] temp = new int[n][n];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            temp[j][n - i - 1] = matrix[i][j];
        }
    }
    for (int i = 0; i < temp.length; i++) {
        System.arraycopy(temp[i], 0, matrix[i], 0, temp.length);
    }
}

复杂度
时间复杂度：O(2n^2)，即 O(n^2)
空间复杂度：O(n^2)，多了个临时的矩阵

解法 2：拆解成主对对角对称 + 左右旋转最优解

[旋转图像

操作分解

超简洁易懂的代码【c++/java详细题解】](https://leetcode.cn/problems/rotate-image/solution/48-xuan-zhuan-tu-xiang-chao-jian-ji-yi-d-nuau/)

思路

旋转 90° 可以理解为：主对角线旋转 + 左右旋转
首先主对象旋转，等式为 matrix[i][j] = matrix[j][i]，只需要对象线的上半部分替换即可，所以二层循环的条件为 j<i
再进行左右旋转，这里我们采用首尾双指针来进行替换

代码

  
public static void rotate(int[][] matrix) {
    int n = matrix.length;
    // 主对角线旋转（左上→右下对角线）
    for (int i = 0; i < n; i++) {
```java
for (int j = 0; j < matrix.length; j++) { // 不用这个遍历条件，主要是考虑对角线替换只需要上半部分即可。
	for (int j = 0; j < i; j++) {
            // 两个交换下位置
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 左右旋转（以中线）
    for (int i = 0; i < n; i++) {
        for (int start = 0, end = n - 1; start < end; start++, end--) {
            // 首尾交换
            int temp = matrix[i][start];
            matrix[i][start] = matrix[i][end];
            matrix[i][end] = temp;
        }
    }
}

复杂度
时间复杂度：O(2n^2)，即 O(n^2)
空间复杂度：O(1)，无需临时的矩阵，原地翻转替换

螺旋矩阵相关

54. 螺旋矩阵 medium

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

解法 1：按层模拟，设定边界

思路

可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界：

随着螺旋遍历，相应的边界会收缩，直到螺旋遍历完整个数组：

代码

  
public List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    // 1、定义四个边的边界
    int top = 0;
    int right = n - 1;
    int bottom = m - 1;
    int left = 0;
    List<Integer> res = new ArrayList<>();
    while (res.size() < m * n) {
        // 1、先添加上边（左→右）
        if (top <= bottom) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            // 上边界下移
            top++;
        }
        // 2、再添加右边（上→下）
        if (right >= left) {
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            // 右边界左移
            right--;
        }
        // 3、再添加下边（右→左）
        if (bottom >= top) {
            for (int i = right; i >= left; i--) {
                res.add(matrix[bottom][i]);
            }
            // 下边界上移
            bottom--;
        }
        // 4、最后添加左边（下→上）
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                res.add(matrix[i][left]);
            }
            // 左边界右移
            left++;
        }
    }
    return res;
}

复杂度

时间复杂度 O(mn) mn 为矩阵的行和列
空间复杂度 O(1)

59. 螺旋矩阵II(根据二维数组顺时针生成螺旋数组) medium

题目

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]

解法 1：按层模拟，设定边界

思路：

主要思路和 54 题的类似，54 题是根据矩阵输出到二维数组；而该题是反过来，根据二维数组生成螺转矩阵
先生成最外层，再逐步生成内层

代码

  
public int[][] generateMatrix(int n) {
    // 1、定义四个边的边界
    int top = 0;
    int right = n - 1;
    int bottom = n - 1;
    int left = 0;
    // 需要填入到matrix的数字
    int num = 1;
    int[][] matrix = new int[n][n];
    while (num < n * n) {
        // 上边界
        if (top <= bottom) {
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
        }
        // 右边界
        if (right >= left) {
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
        }
        // 下边界
        if (bottom >= top) {
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
        }
        // 左边界
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
    }
    return matrix;
}

数组其他面试题

88. 合并两个有序数组 easy

题目

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解法 1：临时数组 + 双指针

思路

临时数组 temp；双指针 p1、p2，p1 指向 nums1 数组，p2 指向 nums2 数组
遍历数组，比较 p1 和 p2 位置元素大小，小的元素放入 temp，p1 和 p2 指针往前移动
nums1 未遍历完成，剩余的元素都加到 temp 后；nums2 未遍历完成，剩余的元素都加到 temp 后
将 temp 的元素拷贝到 nums1

代码 1

  
public static void merge(int[] nums1, int m, int[] nums2, int n) {
    if (n == 0) return;
    // 临时数组
    int[] temp = new int[m + n];
    int p1 = 0;
    int p2 = 0;
    int i = 0;
    while (p1 < m && p2 < n) {
        if (nums1[p1] <= nums2[p2]) {
            temp[i] = nums1[p1];
            p1++;
        } else {
            temp[i] = nums2[p2];
            p2++;
        }
        i++;
    }
    // arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
    // nums1还有数据
    if (p1 < m) {
        System.arraycopy(nums1, p1, temp, i, m - p1);
    } else if (p2 < n) {
        // nums2还有数据
        System.arraycopy(nums2, p2, temp, i, n - p2);
    }
    // temp赋值给nums1
    System.arraycopy(temp, 0, nums1, 0, temp.length);
}

复杂度

时间复杂度 O(2(m+n))，需要遍历数组 nums1 和 nums2 两次
空间复杂度 O(m+n)

解法 2：倒序插入法（最优解）

思路

倒序遍历，将大的值插入到 nums1 的最后面
依次遍历，直到 nums1 或 nums2 遍历完毕后 (m>0 && n>0)
1. nums1 和 nums2 未遍历完毕时，比较 nums1 和 nums2 当前位置谁大，大的就插入到 nums1 尾部；尾部的索引为 m+n-1；nums1 的值大就 m–，nums2 的值大就 n–
2. 如果 nums2 的先遍历完毕，只剩下 nums1 了，这种情况不需要处理，因为本来就是将值插入到 nums1 后面
3. 如果 nums1 的先遍历完毕，只剩下 nums2 了，那么只需要将 nums2 剩下的元素复制到 nums1 即可
nums1 就是合并后的数据

代码 1

  
public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int index = m + n - 1;
    while (m > 0 && n > 0) {
        if (nums1[m - 1] >= nums2[n - 1]) {
            nums1[index] = nums1[m - 1];
            m--;
        } else {
            nums1[index] = nums2[n - 1];
            n--;
        }
        index--;
    }
    // 如果nums2先摆完，那么nums1就不需要管了
    // 如果nums1先摆完，那么现在需要把nums2复制到nums1中去
    for (int i = 0; i < n; i++) {
        nums1[i] = nums2[i];
    }
}

代码 2（最优解）

  
public static void merge(int[] nums1, int m, int[] nums2, int n) {
    while (m > 0 && n > 0) {
        if (nums1[m - 1] >= nums2[n - 1]) {
            nums1[m + n - 1] = nums1[m - 1];
            m--;
        } else {
            nums1[m + n - 1] = nums2[n - 1];
            n--;
        }
    }
    // 如果nums2先摆完，那么nums1就不需要管了
    // 如果nums1先摆完，那么现在需要把nums2复制到nums1中去
    for (int i = 0; i < n; i++) {
        nums1[i] = nums2[i];
    }
}

复杂度

时间复杂度 O(m+n) m 和 n 分别为 nums1 和 nums2 的数组长度
空间复杂度 O(1)

189. 轮转数组 medium

题目：

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。输入: 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]

1. 额外的数组

使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)%arr.length 的位置，最后将新数组拷贝至原数组即可。

  
public static void rotate(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return;
    }
    if (k % arr.length == 0) return; // n是k的因树
    int n = arr.length;
    if (k > n) return;
    int[] temp = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        int index = (i + k) % n;
        temp[index] = arr[i];
    }
    System.arraycopy(temp, 0, arr, 0, n);
}

时间、空间复杂度都是 O(n)
缺点：多了临时数组，使空间复杂度变成了 O(n)

2. 数组 3 次翻转

思路

全局翻转
左边 k 项翻转
右边 n-k 项翻转

案例：
1,2,3,4,5,6,7, k=5
结果为：3,4,5,6,7,1,2

全部反转: 7,6,5,4,3,2,1
前 k 个元素一组，后 n-k 个元素一组反转：3,4,5,6,7,1,2

代码：

  
public static void rotate(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return;
    }
    if (k % arr.length == 0) return; // n是k的因树
    int n = arr.length - 1; 
    k = k % arr.length; // 保证k大于arr.length时也能运行
    // 全局翻转
    reverse(arr, 0, n);
    // 翻转[0,k-1]个位置
    reverse(arr, 0, k - 1);
    // 翻转[k,n]个位置
    reverse(arr, k, n);
}

private static void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

时间复杂度：O(n)，其中 n 为数组的长度。每个元素被翻转两次，一共 n 个元素，
因此总时间复杂度为 O(2n)=O(n)。
空间复杂度：O(1)
缺点：遍历了 2 次
那有没有只需要遍历 1 次，空间复杂度 O(1) 的方案呢，有那就是环形替换。

3、环形替换（原地替换，最优解）

力扣
思路：

方法 1(额外数组) 在 i 索引处移动 k 步后，会将 pos=(i+k)%len 处的元素给覆盖掉（pos 为即将要被替换的索引处）
那么我们是不是可以用个临时变量 temp 记录下 pos 处要被覆盖的元素（替换后用 pre 指向记录），pre 记录 i 处的元素
pos 处的元素用 pre 替换掉，pre 记录 temp，以便于下一轮替换用
pos 继续走 k 步，其实就是个环形替换的过程
直到所有的元素都替换完毕 (用个 count 遍历记录遍历的次数，需要遍历 arr.length 次)
需要注意，如果 k 是 arr.length 的因子，就会出现只在某几个位置上替换，其他的元素不会替换到

会存在一个问题，当 k 为 n 的因子时，会出现循环情况，例如从 0 开始移动数组，最终会再回到 0，而无法对其他的元素进行修改；此时只需要从 i=0 的下一个元素，即 i=1 开始移动数组元素即可，可以证明不会出现重叠的情况，只需循环到 i==k 时，即终止循环，nums 所有的元素移动完毕。

因子就是所有可以整除这个数的数,不包括这个数自身.（就是一个数的约数，比如 20 的因子有 1 2 4 5 10 20）因数包括这个数本身而因子不包括, 如：比如 15 的因子是 1,3,5 　　而因数为 1,3,5,15.　　完数是指此数的所有因子之和等于此数,例如：28=1+2+4+7+14.

代码

  
public static void rotate3(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return;
    }
    if (k % arr.length == 0) return; // n是k的因树
    int len = arr.length;
    k = k % len; // 防止k大于arr长度
    int count = 0; // 记录要替换的次数，数组中的每个数都需要替换，为arr.length
    int pre = arr[0]; // 保存要移动的元素，用于给后面的pos+k处替换用的
    int pos = 0; // 即将要被替换的位置，默认从0开始
    int i = 0; // 出现死循环替换时，需要往前移动一步
    while (count < len) {
        pos = (pos + k) % len; // 每次移动k步
        int temp = arr[pos]; // 即将被覆盖的元素
        arr[pos] = pre; // 将pos处替换成为pre元素
        pre = temp; // pre记录刚刚被替换掉的元素temp
        if (i == pos) { // 说明出现了死循环替换了
            i++;
            pos = i;
            pre = arr[pos];
        }
        count++; // 替换完一个元素+1
    }
}

时间复杂度分析：O(n)
空间复杂度分析：O(1)

66. 加一 easy

题目：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

解法 1：carry=1 解法

思路

把加 1 当成是进位的 1，即默认 carry=1
倒序遍历数组，判断 carry==0 情况
1. 如果 carry=0 成立，说明没进位，整个循环遍历结束
2. 如果 carry=1，有进位，判断当前位是否是 9，如果不是 9，不需要进位，当前位加 1，carry 置为 0
3. 如果 carry=1，当前位是 9，当前位置为 0，carry 保持不变为 1
如果能正常循环结束后，carry=1，说明多了一个进位 1(如 999 这种情况)；那么 new 一个新的数组存进制位 1

代码

  
public static int[] plusOne(int[] digits) {
    // 边界条件判断
    if (digits == null || digits.length == 0) return digits;

    int carry = 1;
    // 倒序遍历
    for (int i = digits.length - 1; i >= 0; i--) {
        int digit = digits[i];
        if (carry == 0) break;
        if (digit != 9) { // 不需要进位
            // 当前位保持不变，carry=0(只有carry=1的时候才需要加1)
            digits[i] = digits[i] + 1;
            carry = 0;

        } else { // 需要进位
            // 当前位设置为0，carry为1
            digits[i] = 0;
        }
    }
    System.out.println("=====原始digits=" + System.identityHashCode(digits));
    if (carry == 1) { // 还有进位，需要补
        //            int[] dst = new int[digits.length + 1];
        //            dst[0] = 1;
        //            System.arraycopy(digits, 0, dst, 1, digits.length);
        digits = new int[digits.length + 1]; // 等价于上面；为啥不需要重新赋值
        System.out.println("=====扩容后digits=" + System.identityHashCode(digits));
        digits[0] = 1;
    }
    return digits;
}

解法 2

画解算法：66. 加一

末位无进位，则末位加一即可，因为末位无进位，前面也不可能产生进位，比如 45 => 46
末位有进位，在中间位置进位停止，则需要找到进位的典型标志，即为当前位 %10 后为 0，则前一位加 1，直到不为 0 为止，比如 499 => 500
末位有进位，并且一直进位到最前方导致结果多出一位，对于这种情况，需要在第 2 种情况遍历结束的基础上，进行单独处理，比如 999 => 1000

  
public static int[] plusOne(int[] digits) {
    // 边界条件判断
    if (digits == null || digits.length == 0) return digits;

    // 倒序遍历
    for (int i = digits.length - 1; i >= 0; i--) {
        // 1、先加1
        digits[i]++;
        // 2、对加1后和10取余，看是否有进位
        digits[i] %= 10;
        // 3、看是否有进位
        if (digits[i] != 0) { // 不为0表示没有进位，直接返回
            return digits;
        }
    }
    // 走到这里说明有个进位1
    digits = new int[digits.length + 1];
    System.out.println("digits=" + Arrays.toString(digits));
    digits[0] = 1;
    return digits;
}

时间复杂度 O(n)

724. 寻找数组的中心下标 easy

题目：

给你一个整数数组 nums ，请计算数组的中心下标。数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。
输入：nums = [1, 7, 3, 6, 5, 6] 输出：3 解释：中心下标是 3 。左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

前缀和

思路

先计算出数组所有元素之和 total
从左到右遍历数组，记左边元素之和为 sum
假设存在 i 位置 sum+nums[i] = total-sum，那么 i 就为中心下标

  
public static int pivotIndex(int[] nums) {
    if (nums == null || nums.length == 0) return -1; // 边界条件判断
    // 计算出总和
    int total = 0;
    for (int num : nums) {
        total += num;
    }
    int sum = 0; // sum代表左边元素之和
    for (int i = 0; i < nums.length; i++) {
        if (sum + nums[i] == total - sum) { // 左边之和 == 右边之和?
            return i;
        }
        sum += nums[i];
    }
    return -1;
}

解法 2

724. 寻找数组的中心下标（前缀和，清晰图解）
思路

定义 sumLeft 表示左边元素之和，sumRight 表示右边元素之和；默认 sumLeft=0，sumRight 为所有元素之和
从左到右遍历数组 nums
sumLeft 不停的累加，sumRight 不停的减小
直到 sumLeft==sumRight，那么 i 就是中心索引

代码

  
public static int pivotIndex(int[] nums) {
    if (nums == null || nums.length == 0) return -1; // 边界条件判断
    int sumLeft = 0; // 左边总和
    int sumRight = 0; // 右边总和
    for (int num : nums) {
        sumRight += num;
    }
    // 左边扩张，右边压缩，直到左边==右边
    for (int i = 0; i < nums.length; i++) {
        sumRight -= nums[i];
        if (sumRight == sumLeft) {
            return i;
        }
        sumLeft += nums[i];
    }
    return -1;
}

时间复杂度 O(N) ：其中 N 为数组 nums 长度。求和操作使用 O(2N) 线性时间，遍历 nums 最差使用 O(2N) 线性时间。
空间复杂度 O(1) ：变量 sum_left , sum_right 使用常数大小空间。

485. 最大连续 1 的个数 easy

题目

给定一个二进制数组 nums ，计算其中最大连续 1 的个数。 输入： nums = [1,1,0,1,1,1] 输出： 3 解释： 开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

解法 1：一次遍历

思路

只需要一次遍历，用变量 max 记录最大连续 1 的个数，变量 count 记录当前一个连续 1 窗口最大连续 1 的个数
在连续 1 的这个窗口中，每遇到一个 1 就会更新 count 和 max
遍历结束后，方法 max 即可

代码

  
public static int findMaxConsecutiveOnes(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int max = 0; // 记录最大连续1的个数
    int count = 0; // 记录当前窗口中1连续的个数
    for (int num : nums) {
        if (num == 0) {
            count = 0;
        } else {
            count++;
            max = Math.max(count, max);
        }
    }
    return max;
}

时间复杂度 O(n)，空间复杂度 O(1)

解法 2：滑动窗口法

思路

当前窗口只维护着连续的 1，l 代表窗口左边，r 代表窗口右边，max 记录所有窗口中最大连续 1 的个数
如果连续都是 1，不停的更新 r++ 使窗口不断向右扩张；当出现不是 1 的时候，计算当前窗口连续 1 的个数 r-l，并和 max 比较，将最大的值赋值给 max
当 r>=n 时，遍历结束，返回 max 即可

代码

  
public static int findMaxConsecutiveOnes(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    // 记录最大连续1的个数
    int max = 0;
    // 窗口的左边
    int l = 0;
    // 窗口的右边
    int r = 0;

    while (r < n) {
        if (nums[r] == 1) { // 如果为1，则窗口右边不断向右扩大
            r++;
        } else { // 如果为0
            // 算下最大连续1的个数
            max = Math.max(max, r - l);
            // 窗口需要重新计算
            r++;
            l = r; // 更新窗口的左边
        }
    }
    // 再次计算下
    max = Math.max(max, r - l);
    return max;
}

时间复杂度 O(n)，空间复杂度 O(1)
给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/product-of-array-except-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

238. 除自身以外数组的乘积 medium

题目

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。 示例 1：输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0] 示例 2：输入: nums = [1,2,3,4] 输出: [24,12,8,6]

思考
可以用暴力解法，循环遍历 2 次，但时间复杂度 O(n^2) 太高通不过；也可以先将所有元素的乘积起来然后计算 i 位置除以该位置元素即可，但如果出现为 0 就不行了，而且题目也要求不能用 0

解法 1：左右乘积法

思路

用 2 个数组 L 和 R，L 数组记录 i 位置左边所有元素的乘积（不包括 i 位置本身，比如 L[0]=1,0 位置没有左边元素），R 数组记录 i 位置右边所有元素的乘积 (R[len-1]=1)；额外记录结果的数组 result
循环遍历数组，第 i 个位置的除自身以外数组的乘积就是 result[i] = L[i] * R[i]
返回 result

代码

  
public static int[] productExceptSelf3(int[] nums) {
    // 边界条件判断
    if (nums == null || nums.length == 0) return nums;
    int len = nums.length;

    // L 和 R 分别表示左右两侧的乘积列表
    int[] L = new int[len];
    int[] R = new int[len];
    int[] result = new int[len];

    // L[i] 为索引 i 左侧所有元素的乘积
    // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
    L[0] = 1;
    for (int i = 1; i < len; i++) {
        L[i] = nums[i - 1] * L[i - 1];
    }

    // R[i] 为索引 i 右侧所有元素的乘积
    // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
    R[len - 1] = 1;
    for (int i = len - 2; i >= 0; i--) {
        R[i] = nums[i + 1] * R[i + 1];
    }

    // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
    for (int i = 0; i < len; i++) {
        result[i] = L[i] * R[i];
    }
    return result;
}

复杂度
时间复杂度：O(3n)，3 次循环，根据大 O 法，记为 O(n)
空间复杂度：O(2n)，2 个额外数组，记为 O(n)

解法 2：动态右乘积空间复杂度 O(1) 的方法（最优解）

思路
左右乘积法的空间复杂度为 O(n)，我们可以用右乘积动态计算来实现，result 用作左乘积来达到 O(1) 的空间复杂度

记录结果的 result 数组，这个是不算到空间复杂度去的，所以我们可以先用这个数组来存左乘积的结果
右乘积不定义新的数组存储，而是动态计算出来；R 代表当前位置的右乘积，计算公式为 R=R*nums[i]
倒序遍历 nums，result[i] = result[i] * R 可以计算出该位置的乘积，同时计算出下一个位置的乘积 R=R*nums[i]

代码

  
public static int[] productExceptSelf(int[] nums) {
    // 边界条件判断
    if (nums == null || nums.length == 0) return nums;
    int len = nums.length;

    int[] result = new int[len];
    result[0] = 1;
    for (int i = 1; i < len; i++) {
        result[i] = nums[i - 1] * result[i - 1];
    }

    int R = 1;
    for (int i = len - 1; i >= 0; i--) {
        result[i] = result[i] * R;
        R = R * nums[i];
    }
    return result;
}

复杂度
时间复杂度：O(N)，其中 NN 指的是数组 nums 的大小。分析与方法一相同。
空间复杂度：O(1)，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。

比较版本号

BM22 比较版本号

按.切割数组比较

双指针比较

  
public static int compare(String version1, String version2) {
    int len1 = version1.length();
    int len2 = version2.length();
    int p1 = 0; // 指向version1头部
    int p2 = 0; // 指向version2头部

    char[] char1 = version1.toCharArray();
    char[] char2 = version2.toCharArray();
    // 按.找到分组，逐个来比较
    while (p1 < len1 || p2 < len2) {
        long v1 = 0;
        while (p1 < len1 && char1[p1] != '.') {
            v1 = v1 * 10 + (char1[p1] - '0');
            p1++;
        }

        long v2 = 0;
        while (p2 < len2 && char2[p2] != '.') {
            v2 = v2 * 10 + (char2[p2] - '0');
        } if (v1 > v2) {
            return 1;
        } else if (v1 < v2) {
            return -1;
        }
        p1++;
        p2++;
    }
    return 0;
}

数组中的逆序对

  
private int count = 0;

public int InversePairs(int[] array) {
    int low = 0;
    int high = array.length - 1;

    mergeSort(array, low, high);
    System.out.println("总逆序个数count=" + count);
    return count;
}

public void mergeSort(int[] arr, int low, int high) {
    if (low >= high) { // 只有1个元素了，不划分了
        return;
    }

    // 拆分
    int mid = low + (high - low) / 2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    // 合并
    int l = low; // 指向左子数组指针开始位置
    int r = mid + 1; // 指向右子数组指针开始位置
    int tempIndex = l; // 辅助数组指针，指向左子数组开始位置
    int[] temp = new int[arr.length];
    while (l <= mid && r <= high) {
        if (arr[l] <= arr[r]) {
            temp[tempIndex++] = arr[l++];
        } else {
            // 存在逆序对
            count += mid - l + 1;
            count %= 1000000007;
            temp[tempIndex++] = arr[r++];
        }
    }

    // 左边剩下的，全部合并到temp
    while (l <= mid) {
        temp[tempIndex++] = arr[l++];
    }
    // 右边剩下的，全部合并到temp
    while (r <= high) {
        temp[tempIndex++] = arr[r++];
    }

    // 再将temp拷贝到aar数组对应的位置
    int index = low;
    while (index <= high) {
//            arr[index++] = temp[index++]; // 不能这样写，这样index多加了1
        arr[index] = temp[index];
        index++;
    }
    System.out.println("count=" + count + ",low=" + low + ",high=" + high + ",temp=" + Arrays.toString(temp) + ", aar=" + Arrays.toString(arr));
}

接雨水

暴力
双指针

不用循环找数组最大值

思路：从数组后往前递归，每次递归都找到最大值，并传递给下一次递归，当索引小于 0 时，递归结束，方法递归过程中的最大值即可。

  
/**
 * 使用递归来代替for
 */
public static int find(int[] arr) {
    if (arr.length <= 0) {
        throw new IndexOutOfBoundsException("arr不能为空");
    }
    //       return find(arr, arr.length - 1, arr[arr.length - 1]);
    return find1(arr, 0, arr[0]);
}
/**
 * 递归的从后往前找最大值，最大值记录在lastVal变量中
 * 思路：
 * 1. 数组从后往前遍历，每次递归都将最大的值传给下一次递归
 * 2. 递归结束条件是索引小于0了，
 * 3.
 * @param arr       待求数组
 * @param lastIndex 数组最后一个下标
 * @param max       当前最大的值，初始化为组最后一个元素
 */
public static int find(int[] arr, int lastIndex, int max) {
    if (lastIndex >= 0) {
        if (arr[lastIndex] > max) {
            max = arr[lastIndex];
        }
        return find(arr, lastIndex - 1, max);
    } else {
        return max;
    }
}

75. 颜色分类

题目

颜色分类。题目难度为 Medium，目前通过率为 51.8% 。给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。 2022 年 6 月 20 日字节一面 - 开放平台面试题

解法 1：计数法

遍历一遍数组，把红色和白色的球数量找出来，用 2 个 int 变量存起来 redCount 和 whiteCount
再一次循环，将数组中的元素重新设置值

  
public void sort0(int[] arr) {
    int redCount = 0;
    int whiteCount = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) {
            redCount++;
        } else if (arr[i] == 1) {
            whiteCount++;
        }
    }
    for (int i = 0; i < arr.length; i++) {
        if (i < redCount) {
            arr[i] = 0;
        } else if (i < redCount + whiteCount) {
            arr[i] = 1;
        } else {
            arr[i] = 2;
    }
 }

时间复杂度为：O(2n)

解法 2：双指针法

left 指针指向红色球 0 最后出现的位置的下一个索引；right 指针指向蓝色球 2 的索引位置
遍历数组，循环条件为 i<=right
如果遇到为 0，交换当前位置和 left 元素，让 left++；如果遇到为 2 的话，交换当前位置和 right 元素，因为交换了位置后的元素未参与计算，所以 left— 需要重新计算下，right–
最后循环

  
public void sort(int[] nums) {
    if (nums.length <= 0) return;
    int left = 0;// 记录0最后的位置的下一个位置，不能为-1，为-1的话，[2, 1, 2, 2, 0, 2, 1, 1, 0]这种就会排序后=[0, 0, 1, 1, 1, 2, 2, 2, 2]
    int right = nums.length - 1;
    for (int i = 0; i <= right; i++) {
        int num = nums[i];
        if (num == 0) { // 为0，和left交换，将0交换到最前面
            swap(nums, left, i);
            left++;
        } else if (num == 2) { // 为2，和right交换，将2交换到最后面
            swap(nums, right, i);
            right--;
            // 交换后的数据还需要判断一次，所以让i--
            i--;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    if (i == j) return;
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4. 寻找两个正序数组的中位数 hard

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log (m+n)) 。

解法 1：先合并到临时数组再取中间值：时间复杂度为 O(m+n)

用一个临时的数组 num
将两个数组合并成一个数组（这个可以采用倒序插入数组法）
根据奇还是偶数取中间值

  
public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    // 合并成一个数组，取中间的值
    int[] num = new int[m + n];
    int p1 = 0;
    int p2 = 0;
    int i = 0;
    while (p1 < m && p2 < n) {
        if (nums1[p1] <= nums2[p2]) {
            num[i] = nums1[p1];
            p1++;
        } else {
            num[i] = nums2[p2];
            p2++;
        }
        i++;
    }
    if (p1 < m) {
        while (p1 < m) {
            num[i] = nums1[p1];
            p1++;
            i++;
        }
    }

    if (p2 < n) {
        while (p2 < n) {
            num[i] = nums2[p2];
            p2++;
            i++;
        }
    }
    int even = (m + n) % 2;
    if (even == 0) {
        return (num[(m + n) / 2 - 1] + num[(m + n) / 2]) / 2.0;
    } else {
        return num[(m + n) / 2];
    }
}

解法 2：双指针取第 k 个值

先计算出中间值
不停地从 nums1 和 nums2 中取值，直到到中间值
要注意区分奇数和偶数

  
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
    if (nums1.length == 0 || nums2.length == 1) return nums2[0];
    if (nums1.length == 1 || nums2.length == 0) return nums1[0];
    int m = nums1.length;
    int n = nums2.length;
    int p1 = 0;
    int p2 = 0;

    int even = (m + n) % 2;
    int i = 0;
    int mid = (m + n - 1) / 2;
    if (even == 0) { // 偶数
        int pre = 0;
        int cur = 0;
        while (i <= mid + 1) {
            if (p1 < m && nums1[p1] <= nums2[p2]) {
                pre = cur;
                cur = nums1[p1];
                p1++;
            } else if (p2 < n) {
                pre = cur;
                cur = nums2[p2];
                p2++;
            }
            i++;
        }
        return (pre + cur) / 2.0;
    } else { // 奇数
        int cur = 0;
        while (i <= mid) {
            if (p1 < m && nums1[p1] <= nums2[p2]) {
                cur = nums1[p1];
                p1++;
            } else if (p2 < n) {
                cur = nums2[p2];
                p2++;
            }
            i++;
        }
        return cur;
    }
}

53. 最大子数组和 medum

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 **是数组中的一个连续部分。 **输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

解法 1：动态规划

经典动态规划问题（理解「无后效性」）
思路

定义状态（定义子问题）dp[i]：表示以 nums[i] 结尾的连续子数组的最大和
状态转移方程（描述子问题之间的联系）
1. dp[i-1]>0 dp[i] = dp[i-1] + nums[i]
2. dp[i-1]<=0 dp[i] = nums[i]
3. 求最大值：dp[i] = max(nums[i], dp[i-1]+nums[i])
初始化
1. dp[0] = nums[0]

代码 1：无优化版

  
public static int maxSubArray(int[] nums) {
    // 定义状态dp[i] 表示以nums[i]结尾的最大子数组和
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < nums.length; i++) {
        if (dp[i - 1] >= 0) {
            dp[i] = dp[i - 1] + nums[i];
        } else {
            dp[i] = nums[i];
        }
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

代码 2：优化后的空间最优解
根据「状态转移方程」，dp[i] 的值只和 dp[i - 1] 有关，因此可以使用「滚动变量」的方式将代码进行优化。

  
public int maxSubArray(int[] nums) {
    int pre = 0;
    int res = nums[0];
    for (int num : nums) {
        pre = Math.max(pre + num, num);
        res = Math.max(res, pre);
    }
    return res;
}

解法 2：滑动窗口

思路

滑动窗口解题思路关键是要确定能否收缩窗口？我们在窗口内的数据小于 0 的时候收缩就好了
窗口元素之和大于等于 0 时扩大窗口；窗口元素之和小于 0 时候收缩窗口
1. 全部是负数，那每次循环都走收缩窗口逻辑，windowSum 会一直为 0，因为每次收缩窗口后 windowSum 都会变成 0
2. 有正数有负数，那个最大的子数组一定是以正数开头（负数开头的就会收缩窗口给去掉了）
3. 其实就是在穷举所有正数开头的子数组，寻找子数组和最大的那个

代码

  
public static int maxSubArray(int[] nums) {
    int left = 0;
    int right = 0;
    // 当前窗口：窗口中所有元素的和（如果需要找出来子数组元素，那就用map）
    int windowSum = 0;
    int maxSum = Integer.MIN_VALUE;
    while (right < nums.length) {
        // 扩大窗口 & 更新窗口
        windowSum += nums[right];
        right++;
        // 计算最大值
        maxSum = Math.max(maxSum, windowSum);
        // 窗口是否要收缩，小于0的时候收缩
        while (windowSum < 0) {
            windowSum -= nums[left];
            left++;
        }
    }
    return maxSum;
}

变种：不是返回最大子数组和，而是要返回和最大的连续子数组

思路

动态规划，dp[i] 表以 nums[i] 结尾的最大子数组和
临时变量 start 和 len 分别记录当前连续子数组起始位置和长度；maxStart 和 maxLen 记录最大连续子数组和的起始位置和长度；maxSum 记录最大连续子数组和
遍历数组
1. dp[i-1]>0，加上 nums[i] 比之前的大，dp[i]=dp[i-1]+nums[i]；最大子数组扩大，len++，
2. dp[i]<=0，加上 nums[i] 不比之前的大，dp[i]=nums[i]；最大子数组从头开始，start=i, len=1
3. 每趟变量，更新 maxSum，如果当前 dp[i] 为最大子数组和，那么需要更新 maxStart 和 maxLen
nums 数组的 [maxStart,maxStart+maxLen] 即为和最大的子数组和；maxSum 为最大的子数组和

  
public static int maxSubArray(int[] nums) {
    // dp[i]代表着以nums[i]结尾的最大子数组和
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = dp[0];

    // 继续最大子数组和的开始位置和长度
    int maxStart = 0;
    int maxLen = 0;

    // 记录连续子序列的起点和长度
    int start = 0;
    int len = 1;

    for (int i = 1; i < nums.length; i++) {
        if (dp[i - 1] >= 0) { // 大于0，相当于dp[i-1] + nums[i] > nums[i]
            dp[i] = dp[i - 1] + nums[i];
            len++;
        } else { // 遇到了负数，重新开始
            dp[i] = nums[i];
            start = i;
            len = 1;
        }
        if (dp[i] > maxSum) {
            maxSum = dp[i];
            maxStart = start;
            maxLen = len;
        }
    }
    System.out.println("maxSum=" + maxSum + ",maxStart=" + maxStart + ",maxLen=" + maxLen + "，max array=" + Arrays.toString(Arrays.copyOfRange(nums, maxStart, maxStart + maxLen)));
    return maxSum;
}

数据结构和算法, 基础

数据结构和算法数组

本文由作者按照 CC BY 4.0 进行授权

数组快慢指针/双指针相关题

26. 删除有序数组中的重复项(保留一个) easy 快慢指针

解法 1：暴力 TreeSet

解法 2：双指针

解法 3：解法 2 优化版 最优解

27. 移除元素（不保留元素，对顺序无要求）easy 快慢指针

解法 1：双指针

解法 2：双指针优化版本 最优解

283. 移动零(不保留元素，对顺序有要求) easy

解法 1：快慢指针，两次遍历

解法 2：类快速排序 partition，一次遍历

前缀和

303. 区域和检索 - 数组不可变 一维数组前缀和 easy

解法 1：暴力

解法 2：前缀和

304. 二维区域和检索 - 矩阵不可变

解法 1：二维前缀和

滑动窗口相关题

nSum 问题

两数之和

两数之和等于 target（有无重复元素都行）easy

1. 两数之和(有无重复值、无序数组、返回索引)

167. 两数之和 II - 输入有序数组（有序，返回索引）

剑指 Offer 57. 和为s的两个数字（有序，返回元素）

解法 1：哈希表

解法 2：双指针 最优解

两数之和变种

两数之和等于 target 的不重复组合数目（存在重复数） medium

三数之和

15. 三数之和 medium

解法 1：排序、对每个元素求两数之和、去重

解法 2：排序 + 双指针 对解法 1 的条件增强（最右解）

16. 最接近的三数之和 medium

解法 1：排序 + 双指针

四数之和

18. 四数之和 medium

nSum n 数之和

矩阵 (二维数组) 题

矩阵旋转相关

48. 旋转图像 medium

解法 1：临时矩阵

解法 2：拆解成主对对角对称 + 左右旋转 最优解

螺旋矩阵相关

54. 螺旋矩阵 medium

解法 1：按层模拟，设定边界

59. 螺旋矩阵II(根据二维数组顺时针生成螺旋数组) medium

解法 1：按层模拟，设定边界

数组其他面试题

88. 合并两个有序数组 easy

解法 1：临时数组 + 双指针

解法 2：倒序插入法（最优解）

189. 轮转数组 medium

1. 额外的数组

2. 数组 3 次翻转

3、环形替换（原地替换，最优解）

66. 加一 easy

解法 1：carry=1 解法

解法 2

724. 寻找数组的中心下标 easy

前缀和

解法 2

485. 最大连续 1 的个数 easy

解法 1：一次遍历

解法 2：滑动窗口法

238. 除自身以外数组的乘积 medium

解法 1：左右乘积法

解法 2：动态右乘积 空间复杂度 O(1) 的方法（最优解）

比较版本号

按.切割数组比较

双指针比较

数组中的逆序对

接雨水

不用循环找数组最大值

75. 颜色分类

解法 1：计数法

解法 2：双指针法

4. 寻找两个正序数组的中位数 hard

解法 1：先合并到临时数组再取中间值：时间复杂度为 O(m+n)

解法 2：双指针取第 k 个值

53. 最大子数组和 medum

解法 3：解法 2 优化版最优解

解法 2：双指针优化版本最优解

303. 区域和检索 - 数组不可变一维数组前缀和 easy

解法 2：双指针最优解

解法 2：排序 + 双指针对解法 1 的条件增强（最右解）

解法 2：拆解成主对对角对称 + 左右旋转最优解

解法 2：动态右乘积空间复杂度 O(1) 的方法（最优解）