跳到主要内容

数组算法练习

普通数组类题目通常考察对数组结构的理解，涉及位移、区间合并、前缀/后缀积或原地置换等技巧。

53. 最大子数组和 (Maximum Subarray)​

题目描述​

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解题思路​

使用贪心或动态规划。维护当前子数组的和 pre，如果 pre > 0 则继续累加当前元素，否则丢弃之前的累加，从当前元素重新开始。记录过程中的最大值。

Java 代码实现​

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

56. 合并区间 (Merge Intervals)​

题目描述​

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组。

解题思路​

  1. 按区间的起始位置 start 进行排序。
  2. 遍历排序后的区间。如果当前区间的 start 小于等于结果集中最后一个区间的 end，说明有重叠，更新结果集最后一个区间的 end；否则新增区间。

Java 代码实现​

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = res.get(res.size() - 1);
            if (intervals[i][0] <= last[1]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

189. 轮转数组 (Rotate Array)​

题目描述​

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

解题思路​

使用三次反转法：首先由于 k 可能会大于数组长度，取余数 k %= nums.length。

  1. 反转整个数组。
  2. 反转前 k 个元素。
  3. 反转剩余部分。

Java 代码实现​

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int tmp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = tmp;
        }
    }
}

238. 除自身以外数组的乘积 (Product of Array Except Self)​

题目描述​

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

解题思路​

利用两个方向的前缀积：

  1. answer[i] 先存储 i 左侧所有元素的乘积。
  2. 倒序遍历数组，维护一个右侧积变量，不断同步更新 answer[i]。

Java 代码实现​

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) res[i] = res[i - 1] * nums[i - 1];
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
}

41. 缺失的第一个正数 (First Missing Positive)​

题目描述​

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

解题思路​

原地哈希。尽量让数字 i 出现在下标 i-1 的位置。遍历数组，如果 nums[i] 是正整数且由于 nums[i]-1 小于长度，将其交换到正确的位置。第二次遍历查找第一个位置不对的数。

Java 代码实现​

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
}