04_普通数组

LeetCode Hot 100

---

53. 最大子数组和

难度：中等 | LeetCode 链接

给定一个整数数组 nums，找到一个具有最大和的连续子数组，返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：子数组 [4,-1,2,1] 的和最大，为 6

思路

贪心/动态规划：当前位置的最大子数组和只与前一位置的结果相关。

代码

class Solution {
    public int maxSubArray(int[] nums) {
        // 以i结尾的最大值数组和  
        //pre[i] = max{pre[i-1],nums[i]}
        //求最大数组和，可以计算出每个位置的最大值数组和，再取最大
        int pre = 0;
        int ans = nums[0];
        for(int i=0;i<nums.length;i++){
            pre = Math.max(pre+nums[i],nums[i]);
            ans = Math.max(ans,pre);
        }
        return ans;
    }
}

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

---

56. 合并区间

难度：中等 | LeetCode 链接

以数组 intervals 表示若干个区间，合并所有重叠的区间。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

思路

按起点排序后线性合并。

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        //排序
        Arrays.sort(intervals,(a,b) -> (a[0]-b[0]));
        List<int[]> ans  = new ArrayList<>();
        //循环，判断a[1]和b[0]大小
        for(int i =0;i<intervals.length;i++){
            //如果a[1]>b[0]则可以合并
            int size = ans.size();
            if(size>0&&ans.get(size-1)[1]>=intervals[i][0]){
                //比较a[1]和b[1]哪个大保留哪个
                ans.get(size-1)[1] = Math.max(ans.get(size-1)[1],intervals[i][1]);
            }else{
                //如果a[1]<b[0]则不能合并,添加到list
                ans.add(intervals[i]);
            }
        }
        return ans.toArray(new int[0][]);
    }
}

复杂度：时间 O(n log n)，空间 O(n)

---

189. 轮转数组

难度：中等 | LeetCode 链接

给你一个数组，将数组中的元素向右轮转 k 个位置。

输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]

思路

通过取模计算新索引位置，使用额外数组存储结果后覆盖原数组。

代码

class Solution {
    public void rotate(int[] nums, int k) {
        //计算新索引的位置 i = (i + k)%nums.length
        //索引0-5 移动1位 5 -> (5+1)%6  = 0  0-> (0+1)%6 = 1
        int len = nums.length;
        int[] ans = new int[len];
        for(int i=0;i<len;i++){
            ans[(i+k)%len] = nums[i];
        }
        //覆盖原数组
        //public static void arraycopy(
        // Object src,      // 源数组：要复制的原数组
        // int srcPos,      // 源数组起始位置：从源数组的第几个索引开始复制
        // Object dest,     // 目标数组：复制到的目标数组
        // int destPos,     // 目标数组起始位置：复制到目标数组的第几个索引
        // int length       // 复制长度：要复制的元素个数
        // )
        System.arraycopy(ans,0,nums,0,len);
    }
}

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

---

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

难度：中等 | LeetCode 链接

给你一个数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

输入：nums = [1,2,3,4]
输出：[24,12,8,6]

思路

先算左侧前缀乘积，再从右往左乘上右侧前缀乘积。

代码

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] = res[i] * right;
            right *= nums[i];
        }
        return res;
    }
}

复杂度：时间 O(n)，空间 O(1)（不计输出）

---

41. 缺失的第一个正数

难度：困难 | LeetCode 链接

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

输入：nums = [3,4,-1,1]
输出：2

思路

原地哈希：把 1..n 放到对应下标位置 x -> x-1，再扫一遍找第一个不匹配的位置。

代码

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

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

---

总结

题目	核心技巧	时间	空间
最大子数组和	贪心/DP	O(n)	O(1)
合并区间	排序 + 扫描	O(n log n)	O(n)
轮转数组	三次翻转	O(n)	O(1)
除自身以外数组的乘积	前缀积	O(n)	O(1)
缺失的第一个正数	原地哈希	O(n)	O(1)