数组 - 代码随想录

数组

数组刷题记录，基于代码随想录整理。

  • 704 二分查找（边界定义）
  • 27 移除元素（快慢指针）
  • 977 有序数组平方（双端指针）
  • 209 长度最小子数组（滑动窗口）
  • 59 螺旋矩阵 II（模拟）
  • 58 区间和（前缀和）
  • 44 开发商购买土地（二维切分 + 前缀思想）
  • 二分：704
  • 双指针：27、977
  • 滑动窗口：209
  • 模拟：59
  • 前缀和：58、44

704. 二分查找

问题描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

思路

二分法前提： 数组为有序数组，且无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的；

区间定义： 一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

  • [left, right] ：target 在一个左闭右闭的区间，有如下两点：
    • while (left <= right) 使用 <= ，因为left == right是有意义的，所以使用 <=
    • if (nums[middle] > target) ，right 要赋值为 middle - 1，接下来要查找的左区间结束下标位置就是 middle - 1;
  • [left, right): target 在一个左闭右开的区间里，有如下两点：
    • while (left < right)，这里使用 < ,因为left == right在区间[left, right) 没有意义
    • if (nums[middle] > target), right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0;
        int right = len-1; // 这里定义的是[left，right],故为 len-1;
        while(left <= right){ // 两者相等时依然有效
            int middle = left+(right-left)/2; //// 防止溢出 等同于(left + right)/2
            if(nums[middle] == target){
                return middle;
            }else if (nums[middle] > target){
                right = middle - 1;
            }else{
                left = middle + 1;
            }
        }
        return -1;
    }
};
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0;
        int right = len; // [left,right)
        while(left < right){ // left = right 没有意义，故 '<'
            int middle = left+(right-left)/2;
            if(nums[middle] == target){
                return middle;
            }else if(nums[middle] > target){
                right = middle;
            }else{
                left = middle + 1;
            }
        }
        return -1;
    }
};
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

27. 移除元素

问题描述：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

示例 1：

1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

1
2
3
4
5
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

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

思路

因为数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖，所以引入双指针法；

双指针法： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

  • 快指针：寻找数组的元素 ，若值等于 val 跳过，新数组就是不含有目标元素的数组；
  • 慢指针：指向更新新数组下标的位置；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int fast=0;
        int slow=0;
        while(fast<len){
            if(nums[fast] != val){
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }
};

注意这些实现方法并没有改变元素的相对位置！

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

977.有序数组的平方

问题描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

思路

因为数组是有序的， 负数平方之后可能为最大数，所以数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法 了

  • i 指向起始位置，j 指向终止位置。

  • 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

  • 如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j];

  • 如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i];

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        int i=0;
        int j=len-1;
        int k=len-1;
        vector<int> res(len,0);
        while(i<=j && k>=0){
            if(nums[i]*nums[i] > nums[j]*nums[j]){
                res[k--]=nums[i]*nums[i];
                i++;
            }else{
                res[k--]=nums[j]*nums[j];
                j--;
            }
        }
        return res;
    }
};

209.长度最小的子数组 - 力扣（LeetCode）

问题描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度0。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

滑动窗口：根据当前子序列和大小的情况,不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。

主要确定如下三点：

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

窗口： 满足其和 ≥s 的长度最小的连续子数组。

窗口的起始位置如何移动： 如果当前窗口的值≥s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动： 窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        int sum = 0; //当前滑动窗口内数值之和
        int i = 0; //滑动窗口起始位置
        int len = 0; // 当前滑动窗口的长度
        for(int j=0; j < nums.size(); j++){
            sum += nums[j];
            // 使用while，更新起始位置 i , 不断比较子序列是否符合条件
            while(sum >= target){
                len = j-i+1; // 当前滑动窗口长度
                res = res < len ? res : len;
                sum -= nums[i++];
            }
        }
        return res == INT_MAX ? 0 : res; 
    }
};

59.螺旋矩阵 II - 力扣（LeetCode）

问题描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

img

1
2
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1
2
输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

思路

本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程，由外向内一圈一圈这么画下去。:

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

螺旋矩阵遍历顺序（可折叠）
  1. 左到右填充上边
  2. 上到下填充右边
  3. 右到左填充下边
  4. 下到上填充左边

每一圈结束后收缩边界，继续下一圈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));
        int loop = (n+1)/2; // 向上取整,表示循环多少圈
        int offset = 0; // 每循环一次，边缩小
        int startx = 0, starty = 0; // 每次循环开始的坐标
        int cnt = 1; // 用于计数

        while(loop -- ){
            for(int j=starty; j<n-offset; j++){
                res[startx][j] = cnt++;
            }
            for(int i=startx+1;i<n-offset;i++){
                res[i][n-offset-1] = cnt++;
            }
            for(int j=n-offset-2;j>=starty;j--){
                res[n-offset-1][j] = cnt++;
            }
            for(int i=n-offset-2;i>startx;i--){
                res[i][starty]= cnt++;
            }
            offset++;
            startx++;
            starty++;
        }
        return res;
    }
};

58. 区间和

本题为代码随想录后续扩充题目，还没有视频讲解，顺便让大家练习一下ACM输入输出模式（笔试面试必备）

问题描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入: 第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出: 输出每个指定区间内元素的总和。

输入示例

1
2
3
4
5
6
7
8
5
1
2
3
4
5
0 1
1 3

输出示例

1
2
3
9

提示信息

数据范围：
0 < n <= 100000

思路

前缀和： 重复利用计算过的子数组之和，降低区间查询需要累加计算的次数。在涉及计算区间和的问题时非常有用！

  • 我们先做累加，即 p[i] 表示 下标 0 到 i 的 vec[i] 累加之和。

  • 在vec数组上下标 2 到下标 5 之间的累加和，用 p[5] - p[1] 就可以了。

    1
    2
    3
    p[1] = vec[0] + vec[1];
    p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];
    p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

  • 在使用前缀和的时候，分不清前缀和的区间，建议画一画图，模拟一下 思路会更清晰

前缀和区间示意（可折叠）

以 p[i] 表示 nums[0...i] 之和：

  • 区间 [a,b] 的和为 p[b] - p[a-1]（当 a > 0）
  • 当 a = 0 时，区间和直接是 p[b]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

class Solution{
public:
    vector<long long> prefix;
    void buildPrefix(vector<int> nums){
        int n = nums.size();
        prefix.resize(n);
        prefix[0]=nums[0];
        for(int i=1; i<n; i++){
            prefix[i] = prefix[i-1] + nums[i];
        }
    }
    long long subSum(int a,int b){
        if(a==0) return prefix[b];
        return prefix[b]-prefix[a-1];
    }
};

int main(){
    int n,a,b;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    Solution sol;
    sol.buildPrefix(nums);
    while(cin>>a>>b){
        int res = sol.subSum(a,b);
        cout<<res<<endl;
    }
    return 0;
}

44.开发商购买土地

问题描述

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

输入描述:

  • 第一行输入两个正整数，代表 n 和 m。

  • 接下来的 n 行，每行输出 m 个正整数。

输出描述:

  • 请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

输入示例

1
2
3
4
3 3
1 2 3
2 1 3
1 2 3

输出示例

1
0

提示信息

如果将区域按照如下方式划分：

1 2 | 3
2 1 | 3
1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

数据范围：

1 <= n, m <= 100；
n 和 m 不同时为 1。

思路

本题可以使用前缀和 的思路来求解，先将行方向，和列方向的和求出来用于横切或者纵切，方便知道划分的两个区间的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;

class Solution{
public:
    int minArea(vector<vector<int>> nums){
        int n=nums.size();
        int m=nums[0].size();
        vector<int> h(n,0); // 每行的和
        vector<int> v(m,0); // 每列的和
        int res = INT_MAX;
        int sum = 0;

        //统计总和、每行和、每列和
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                sum += nums[i][j];
                h[i] += nums[i][j];
                v[j] += nums[i][j];
            }
        }

        //尝试横向切（切在第 i 行之后，即第 i+1行上面）
        int h_prefix = 0;
        for(int i=0;i<n-1;i++){
            h_prefix += h[i];
            res = min(res,abs(sum-h_prefix-h_prefix)); 
        }
        
        //尝试纵向切（切在第 j 列之后）
        int v_prefix = 0;
        for(int j=0;j<m-1;j++){
            v_prefix += v[j];
            res = min(res,abs(sum-v_prefix-v_prefix));
        }
        return res;
    }
};

int main(){
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;
    cin>>n>>m;
    vector<vector<int>> nums(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>nums[i][j];
        }
    }
    Solution sol;
    int res = sol.minArea(nums);
    if(res == INT_MAX) printf("输入数据有误");
    else cout<<res<<endl;
    return 0;
}
  • 时间复杂度： O(n^2)

总结

二分法： 左闭右闭（[left,right]）、左闭右开（[left,right)），核心是边界定义与循环条件一致。
双指针法： 用快慢指针在一个循环中完成元素筛选/重排。
滑动窗口： 根据窗口内和的变化，动态移动起点与终点。
前缀和： 预处理累计和，把多次区间查询降为 O(1)。