【代码随想录】数组

发表于 更新于 分类于 阅读次数： 本文字数： 5.3k 阅读时长 ≈ 18 分钟

前言

二刷《代码随想录》数组部分，在第一遍的基础上完善解题思路、补充代码注释、补充算法复杂度分析、查看其它优秀题解。

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标下对应的数据，所以存取操作时间复杂度为O(1)。

插入和删除操作时间复杂度为O(n)，需要移动其它元素。

注意，在C++中使用vector时，底层实现仍然是一段连续空间，只不过对于插入和删除操作存在空间自动管理，要熟知自动管理的大致过程。

二分查找

704.二分查找

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

思路1：如果逐个比较，时间复杂度就是O(n)。并且逐个比较的思路没有使用到“升序”这个特征。

思路2：由于是有序的序列，因此可以尝试使用二分查找。二分查找每次在一段有序序列中查找，即[left, right]。

让目标target与中间下标进行比较，mid = left + (right - left) >> 2。

如果mid下标对应值大于target，由于是有序序列，小于mid下标对应值的元素都在左边，说明下面应该在[left, mid - 1]中查找；否则应该在[mid + 1, right]中继续查找。

注意这里每次查找都是左闭右闭区间，最后的终止条件应该是left大于right，即使left == right，那么mid可以为left==right，仍然可以查找。

（除2可以用右移1表示）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1; // [left, right]
        while (left <= right) {
            int mid = left + ((right - left) >> 1); // the mid index
            int tmp = nums[mid]; // temp target
            if (tmp == target) return mid;
            else if (tmp > target) right = mid - 1; // update right
            else left = mid + 1; // update left
        }

        return -1; // fail to find
    }
};

PS：第二种写法，上面是左闭右闭区间，下面使用左闭右开区间。即每次查找的区间是[left, right)，中间下标仍然是mid。不同的地方在于：如果mid对应的值大于target，此时下次查找的区间应该是[left, mid)，即令right = mid；否则下次查找的区间应该是[mid + 1, right)。还需要注意的是终止条件，终止条件是left == right，此时下标为不在范围内的right。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1; // [left, right]
        while (left <= right) {
            int mid = left + ((right - left) >> 1); // the mid index
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1; // update right
            else left = mid + 1; // update left
        }

        return -1; // fail to find
    }
};

相关题目：

35.搜索插入位置：二分查找法如果查找失败的话就是应该插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1; // 使用左闭右闭区间表示
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }

        // 循环结束时left == right + 1
        return left;
    }
};

34.在排序数组中查找元素的第一个和最后一个位置：相等时继续向左区间找，最终结果就是左边界，继续向右找就是右边界。
找到左右边界之后需要判断边界是否合理。

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result(2, -1);
        
        // 第一部分：寻找左边界
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                right = mid - 1;
                result[0] = mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 循环结束之后左边界要么是没有被赋值，要么是左边界，一定是合法范围

        // 第二部分：寻找右边界
        left = 0;
        right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                left = mid + 1;
                result[1] = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 循环结束之后，右边界要么没有被赋值，要么就是右边界，不会超过数组范围

        // 找到左右边界之后需要进行判断是否合理
        // 左右边界只能是未被赋值或者找到target时的赋值
        if (result[0] == -1 || result[1] == - 1)
            result[0] = result[1] = -1;
        return result;
    }
};

69.x 的平方根：$\sqrt{x}$使用二分法搜索表示为:$k^2\le x$，即在[0, x]中搜索最大的整数值，即右边界

两个int值相乘的取值范围会超过int，应该使用long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x;
        int result = -1;
        while (left <= right) {
            long long mid = left + ((right - left) >> 1);
            long long tmp = mid * mid;
            if (tmp <= x) {
                left = mid + 1;
                result = mid;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
};

367.有效的完全平方数：在[0,num]范围内搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            long long mid = left + ((right - left) >> 1);
            long long tmp = mid * mid;
            if (tmp == num) return true;
            else if (tmp < num) left = mid + 1;
            else right = mid - 1;
        }

        return false;
    }
};

移除元素

27.移除元素：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路1：遍历所有元素（时间复杂度为O(n)），当遇到与val相等的元素时，后面所有元素向前移动一个位置，也就是删除操作（时间复杂度O(n)）。因此总的时间复杂度是O(n^2)。

思路2：采用双指针法，快指针fast和慢指针slow，最开始快慢指针指向开始的位置。遍历所有元素。
慢指针指向的始终是下一个应该保留的元素的位置，也就是最终长度。
判断快指针fast指向的元素，如果该元素与val相等，说明应该是被删除的元素，此时快指针向后移动；
如果该元素与val不相等，说明是应该保留的元素，将其移动到慢指针slow指向的位置，并且快慢指针均向后移动。

时间复杂度O(n)，遍历一次数组；空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow, fast, len;
        slow = fast = 0; // 快慢指针
        len = nums.size();
        while (fast < len) {
            if (nums[fast] == val) {
                // 找到应该被删除的元素
                // 不将其移动到保留元素的位置
                fast++;
            } else {
                // 应该保留的元素移动到保留位置
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
        }

        return slow;
    }
};

相关题目：

26.删除排序数组中的重复项：快慢指针，当快指针元素等于慢指针元素时，就一直向后移动；不等时就让慢指针的下一个元素等于快指针元素，并且快慢指针同时递增。
慢指针始终指向最后一个元素，所以最终长度应该是慢指针加1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;

        int slow, fast;
        slow = fast = 0;
        while (fast < len) {
            if (nums[slow] != nums[fast]) nums[++slow] = nums[fast];
            ++fast;
        }

        return slow + 1;
    }
};

时间复杂度O(n)，所有元素被遍历1次；时间复杂度O(1)

283.移动零：相当于遇到val为0就删除，最后在数组后面全部赋值为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow, fast;
        slow = fast = 0;
        int len = nums.size();

        // 将所有值为0的元素删除
        while (fast < len) {
            if (nums[fast] != 0) nums[slow++] = nums[fast];
            fast++;
        }
        // 将后面的元素都赋值为0
        for (; slow < len; slow++) nums[slow] = 0;
    }
};

时间复杂度O(n)，每个元素遍历一次；空间复杂度O(1)

844.比较含退格的字符串：
思路1：先对字符串s删除退格字符，再对字符串t删除退格字符，最后比较两个字符。

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
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int s_len = s.length();
        int t_len = t.length();
        int slow1, fast1;

        // 处理s中的退格
        slow1 = fast1 = 0;
        while (fast1 < s_len) {
            if (s[fast1] != '#') {
                // slow指向的位置为fast的字符
                s[slow1++] = s[fast1];
            } else {
                // 如果是#慢指针后移一位
                slow1 == 0? slow1 : slow1--;
            }

            fast1++;
        }
        // 处理完成之后slow就是s串后一位

        // 处理t中的退格
        int slow2, fast2;
        slow2 = fast2 = 0;
        while (fast2 < t_len) {
            if (t[fast2] != '#') {
                // slow指向的位置为fast的字符
                t[slow2++] = t[fast2];
            } else {
                // 如果是#慢指针后移一位
                slow2 == 0 ? slow2 : slow2--;
            }
            
            fast2++;
        }

        // 比较两个字符
        if (slow1 != slow2) return false;
        for (int i = 0; i < slow1; i++) {
            if (s[i] != t[i]) return false;
        }

        return true;
    }
};

时间复杂度O(N + M)，分别遍历一次串s和串t，再比较一次串s和t；空间复杂度O(1)

思路2：由于遇到#应该前移，假如比较完前面的字符遇到#则已经比较过的字符没有意义，所以不能从前向后比较，因此考虑逆序比较。
这里的误区是：遇到#不应该立即向前移动，因为#前面仍然可能是#。
所以采取的方式为：del_count（表示应该删除的字符）初始值为0，当遇到#时，则del_count应该加1；当遇到普通字符时，如果del_count为0，那么不需要删除，如果不为0，则当前字符应该删除，并且del_count减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
59
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i, j; // 分别表示两个字符串的下标
        i = s.length() - 1;
        j = t.length() - 1;

        int skips = 0, skipt = 0;

        // 两个指针只要有一个有效就需要进行循环
        // 循环中处理不相等情况
        while (i >= 0 || j >= 0) {
            // 处理退格字符
            // 令指针指向第一个不等于#的字符
            while (i >= 0) {
                if (s[i] == '#') {
                    // 遇到#需要删除的字符计数加1
                    skips++;
                    i--;
                } else {
                    // 遇到普通字符
                    // 如果需要删除的字符数目大于0则跳过一个字符
                    // 否则当前字符就是不应该被删除的字符
                    // 跳出循环
                    if (skips > 0) {
                        i--;
                        skips--;
                    } else break;
                }
            }
            while (j >= 0) {
                if (t[j] == '#') {
                    skipt++;
                    j--;
                } else {
                    if (skipt > 0) {
                        j--;
                        skipt--;
                    } else break;
                }
            }
            // 上面的循环结束之后需要判断i与j是否小于0
            if (i >= 0 && j >= 0) {
                // i与j均指向合法位置
                if (s[i] != t[j]) return false;
            } else {
                // i与j已经有一个小于0
                // 如果另一个大于0
                // 说明仍存在普通字符
                if (i >= 0 || j >= 0) return false;
            }

            i--;
            j--;
        }

        return true;
    }
};

时间复杂度O(N + M)，但是每个字符串只遍历一次，一定比思路1简单；空间复杂度O(1)

977.有序数组的平方：思路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
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        // 旧数组先平方
        for (int i = 0; i < len; i++) nums[i] = nums[i] * nums[i];

        vector<int> result(len, 0); // 初始化新数组
        int left = 0, right = len - 1;
        len--;

        while (left <= right) {
            if (nums[left] <= nums[right]) {
                result[len--] = nums[right];
                right--;
            } else {
                result[len--] = nums[left];
                left++;
            }
        }

        return result;
    }
};

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

思路2：找到负数与非负数之间的分界线，假设为flag。那么平方之后的nums[0]nums[flag - 1]是递增的，[flag]nums[end]也是递增的，就可以利用归并排序进行合并。

时间复杂度O(n)，找分界线为O(n)，归并排序复杂度O(n)；空间复杂度O(n)

有序数组的平方

题目：977，上一小节相关题目

思路1：找到绝对值最小的位置，左右指针从中间相两边，新的数组从小到大增加元素。

思路2：左右指针从最左边和最右边开始，新的数组从最后开始增加大的元素。

时间复杂度O(N + M)。

长度最小的子数组

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

思路1：暴力解法：外层循环遍历每一个元素，内层循环从当前元素向后遍历，找到满足和大于等于s的下标，找到之后的距离就是长度。

时间复杂度O(n^2)；空间复杂度O(1)

思路2：滑动窗口方法，维护一个窗口，窗口有左边界和右边界。

1.窗口里是什么：尚未满足条件的一段元素序列
窗口里面应该是当前子序列

2.什么时候移动左边界：当满足条件时应该一直移动左边界，直到不满足条件
当子序列之和大于等于target时，移动左边界，并且记录此时的窗口大小。
注意这里如果子序列之和如果一直大于等于target，就应该一直移动左边界，直到和小于target。

3.什么时候移动右边界：
每次循环都先向后移动一格。

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
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        int left = 0, right = 0; // 窗口左右边界
        int windows_sum = 0; // 窗口内部元素之和
        int result = INT_MAX;

        while (left <= right && left < len && right < len) {
            // 计算当前累积和
            windows_sum += nums[right];
            // 如果当前序列累计和超过target
            while (windows_sum >= target) {
                // 记录当前长度
                int cur_len = right - left + 1;
                result > cur_len ? result = cur_len : result;

                // 窗口左移需要删除左边元素直到序列和小于target
                windows_sum -= nums[left++];
            }
            
            // 移动右边界
            right++;
        }

        // 边界条件：所有元素加起来都无法满足
        if (result == INT_MAX) return 0;
        else return result;
    }
};

时间复杂度O(n)，每个元素都被操作两次，一次进入滑动窗口，一次出滑动窗口；空间复杂度O(1)

注意边界条件，如果所有元素加起来都不能满足traget，那么应该返回0

904.水果成篮：

1.窗口里面是什么：
窗口里面是：（苹果类型：该类型数目），并且最多只能有两个。
这个数据结构很适合用无序字典unordered_map，因为底层实现是hash table，所以访问元素的时间复杂度是O(1)

2.什么时候移动左边界：
当遇到一种新类型的苹果时，应该向左移动，直到其中一种苹果类型清零。

3.什么时候移动右边界：
每次循环时都向后移动一格右边界

注意由于每棵树只能采摘一个，因此窗口长度就是最大数量

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        unordered_map<int, int> windows; // 窗口，（苹果类型，该类型数目）
        int left = 0, right = 0;
        int result = 0;

        while (right < len) {
            // 将新类型的苹果加入窗口
            windows[fruits[right]]++; // 如果没有这个元素就会初始化并加1

            // 如果窗口中类型多于2
            while (windows.size() > 2) {
                // 出现三种苹果类型
                int k = right - 1;
                int second_class = fruits[k]; // 第二种类别
                while (fruits[k] == second_class) k--;
                // 循环结束之后k是第一种类型苹果的下标
                left = k + 1;
                // 从窗口中删除第一种类型
                windows.erase(fruits[k]);
            }
            
            result = max(result, right - left + 1); // 更新最大总数
            right++; // 移动右边界
        }

        return result;
    }
};

时间复杂度O(n)，每个元素进入和离开窗口；空间复杂度O(1)，最多只有三个键值对

76.最小覆盖子串：
1.窗口里面是什么：
子序列，并且要记录t中字母的出现的次数，这个数据结构使用无序字典，作为目标字典；然后记录子序列中t中字母的出现次数，作为当前字典。

2.什么时候左移：
当前字典与目标字典相同时（O(M)），左移，直到移除一个字典中的元素，这会导致与目标字典不同。

3.什么时候右移：

每次循环向后移动一个

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
class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.length(), m = t.length();
        unordered_map<char, int> target_window, cur_window;
        int valid = 0; // 标志当前窗口中满足条件的字符数量
        // 使用串t初始化目标字典
        for (char c : t) target_window[c]++;

        int left = 0, right = 0; // 窗口左右边界
        int result_start, min_len; // 表示最终字串的起点和长度
        min_len = INT_MAX;

        while (right < n) {
            char c = s[right];

            // 如果字母是t中的一个则更新当前窗口
            if (target_window.count(c) > 0) {
                cur_window[c]++;
                // 只在等于时计数一次
                // 如果大于无需重复计数
                if (cur_window[c] == target_window[c]) valid++;
            }

            // 如果t中字符都被覆盖
            while (valid == target_window.size()) {
                // 记录信息
                int cur_len = right - left + 1;
                if (cur_len < min_len) {
                    min_len = cur_len;
                    result_start = left;
                }

                // 移动左边界
                char d = s[left]; // 被删除的字符
                left++;
                
                // 如果被删除的字符是目标字符
                if (target_window.count(d) > 0) {
                    // 只在刚好等于时计数一次
                    // 如果小于无需重复计数
                    if (cur_window[d] == target_window[d]) valid--;

                    cur_window[d]--;
                }
            }

            right++;
        }

        // 如果没有满足条件的子序列
        if (min_len == INT_MAX) return string();
        else return s.substr(result_start, min_len);
    }
};

关键点：比较当前窗口是否满足目标窗口，这个时间复杂度是O(C)，C表示字符集大小。这里做的优化是，采用一个valid记录当前窗口中满足条件的字符个数，这样在遍历过程中就会更新valid，根据valid来判断是否满足条件，而不是每次都比较两个窗口。

时间复杂度O(n)，左边界和右边界最多都遍历一次所有元素；空间复杂度O(C)，C是字符集大小。

螺旋矩阵

59.螺旋矩阵II

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

思路：这是一种模拟过程类型的题。

首先确定一次循环处理一圈，那么对于奇数和偶数来说，一共需要循环 n / 2（向下取整）圈，但是奇数需要将最后一个元素填充到中心。

接着，一圈也就是一次循环，分别处理上边、右边、下边、左边，对于每一个边来说，处理的范围都是[start, end)，只不过对于行来说，是col移动，对于列来说，是row移动。这个范围每次循环向内收缩。

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int times = n / 2; // 向下整除，循环总次数，也就是圈数
        int start = 0, end = n - 1; // 每一圈的行和列的边界 
        int count = 1; // 每个位置应该填充的数字
        vector<vector<int>> result(n, vector<int>(n, 0));

        while (times-- > 0) {
            // 处理上边
            for (int row = start, col = start; col < end; col++)
                result[row][col] = count++;

            // 处理右边
            for (int row = start, col = end; row < end; row++)
                result[row][col] = count++;
            
            // 处理下边
            for (int row = end, col = end; col > start; col--)
                result[row][col] = count++;
            
            // 处理右边
            for (int row = end, col = start; row > start; row--)
                result[row][col] = count++;
            
            start += 1;
            end -= 1;
        }

        // 对于奇数需要填充最后一个数字
        if (n % 2 == 1) result[start][end] = count;

        return result;
    }
};

时间复杂度O(n^2)，因为外层循环是O(n)，里面的操作是O(n)级别。模拟遍历二维矩阵的时间。

空间复杂度O(n^2)

在循环中需要注意的是：循环不变量，即在一个循环中保持不变的量，比如二分法循环中不变的是左闭右开区间或者左闭右闭区间，比如简单选择排序中不变的是前i个元素是最小的。

在本题中就是每一圈内部，每一行操作的长度均是[start, end)

总结（一刷、二刷）

一共介绍了四种题型和方法，分别是二分法、双指针、滑动窗口、模拟操作（循环不变量）

  • 查找操作：对于有序数组，采用二分查找法，二分查找法的关键在于确定查找区间是左闭右开开始左闭右闭，如果是左闭右开，那么循环条件就是左边界小于右边界，并且循环终止时left = right；
    如果是左闭右闭，那么循环条件就是左边界<=有边界，并且循环终止时left=right+1。
    跳出循环的时候，所有元素都已经比较过，并且如果查找失败跳出循环，此时的下标就应该是这个元素被插入的位置：如果是左闭右开，此时left = right，应该把从right到末尾的元素全部后移；如果是左闭右闭，那么此时left = right + 1，应该把从left到末尾的元素全部后移。
  • 删除操作：由于数组元素不能直接删除，因此只能采取移动覆盖操作。利用双指针法对数组元素进行操作，可以一次性确定保留元素位置和正在遍历位置。
  • 寻找满足条件的连续子序列：采用滑动窗口法框住一部分子序列，当满足条件时记录信息。
  • 模拟数组操作：模拟题目表述的行为，对数组进行操作，这里的关键是搞清楚循环中不变的是什么。