通关算法题之 ⌈数组⌋ 上

滑动窗口

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
1
2

这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了。

唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素的，换句话说收缩完成后一定保证窗口中没有重复。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0, res = 0;
        while(right < s.size()){
            char c = s[right];
            right++;
            window[c]++;
            while(window[c] > 1){
                char d = s[left];
                left++;
                window[d]--;
            }
            res = max(res, right - left);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

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

不过需要强调的是，题目说了 nums 数组中的元素都是正数，有了这个前提才能使用滑动窗口算法，因为窗口扩大时窗口内元素之和必然增大，窗口缩小时窗口内元素之和必然减小。

如果 nums 数组中包含负数，则窗口扩大时元素和不见得就增大，窗口缩小时元素和不见得就减小，这种情况就不能单纯使用滑动窗口技巧了，可能需要混合动态规划和单调队列来做。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0, res = INT_MAX;
        while(right < nums.size()){
            sum += nums[right];
            right++;
            while(sum >= target && left < right){
                res = min(res, right - left);
                sum -= nums[left];
                left++;
            }
        }
        return res == INT_MAX ? 0 : res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t ，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串"" 。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
1
2

滑动窗口的思路：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

初始状态：

增加 right，直到窗口 [left, right) 包含了 T 中所有字符：

现在开始增加 left，缩小窗口 [left, right)：

直到窗口中的字符串不再符合要求，left 不再继续移动：

之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。

首先，初始化 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符：

unordered_map<char, int> need, window;
for (char c : t) need[c]++;
1
2

然后，使用 left 和 right 变量初始化窗口的两端，不要忘了，区间 [left, right) 是左闭右开的，所以初始情况下窗口没有包含任何元素：

int left = 0, right = 0;
int valid = 0; 
while (right < s.size()) {
    // 开始滑动
}
1
2
3
4
5

其中 valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。

如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t){
        need[c]++;
    }
    int left = 0, right = 0, valid = 0; // valid表示窗口中满足 need 条件的字符个数
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }                    
        }
    }
    // 返回最小覆盖子串
    return len == INT_MAX ? "" : s.substr(start, len);
}
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

需要注意的是，当我们发现某个字符在 window 的数量满足了 need 的需要，就要更新 valid，表示有一个字符已经满足要求，而且两次对窗口内数据的更新操作是完全对称的。

当 valid == need.size() 时，说明 T 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。

移动 left 收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
输入：s1= "ab" s2 = "eidboaoo"
输出：false
1
2
3
4

注意哦，输入的 s1 是可以包含重复字符的，所以这个题难度不小。

这种题目，是明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。

2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

class Solution {
public:
    // 判断 s2 中是否存在 s1 的排列
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> need, window;
        for(char c : s1){
            need[c]++;
        }
        int left = 0, right = 0, valid = 0;
        while(right < s2.size()){
            char c = s2[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]) valid++;
            }
            // 判断左侧窗口是否要收缩
            while(valid == need.size()){
                // 判断是否找到了合法的子串
                if(right - left == s1.size()) return true;
                char d = s2[left];
                left++;
                if(need.count(d)){
                    if(window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        // 未找到符合条件的子串
        return false;
    }
};
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

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
1
2

所谓的字母异位词就是排列，相当于输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, window;
        for(char c : p) need[c]++;
        int left = 0, right = 0, valid = 0;
        vector<int> res;
        while(right < s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]) valid++;
            }
            // 判断左侧窗口是否要收缩
            while(valid == need.size()){
                // 当窗口符合条件时，把起始索引加入 res
                if(right - left == p.size()) res.push_back(left);
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(need[d] == window[d]) valid--;
                    window[d]--;
                }
            }
        }
        return res;
    }
};
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

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

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

双指针，滑动窗口。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int left = 1, right = 1, sum = 0;
        vector<vector<int>> res;
        deque<int> add;
        while(left <= target / 2){
            sum += right;
            add.push_back(right);
            right++;
            while(sum >= target){
                if(sum == target){
                    res.push_back(vector<int>(add.begin(), add.end()));
                }
                sum -= left;
                add.pop_front();
                left++;
            }
            
        }
        return res;      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

数组遍历/旋转

BM97 旋转数组

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入：6,2,[1,2,3,4,5,6]
输出：[5,6,1,2,3,4]
1
2

使用三次翻转，思路：

• step 1：因为m可能大于n，因此需要对n取余，因为每次长度为n的旋转数组相当于没有变化；
• step 2：第一次将整个数组翻转，得到数组的逆序，它已经满足了右移的整体出现在了左边；
• step 3：第二次就将左边的m个元素单独翻转，因为它虽然移到了左边，但是逆序了；
• step 4：第三次就将右边的n−m个元素单独翻转，因此这部分也逆序了；

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        //取余，因为每次长度为n的旋转数组相当于没有变化
        m = m % n; 
        //第一次逆转全部数组元素
        reverse(a.begin(), a.end()); 
        //第二次只逆转开头m个
        reverse(a.begin(), a.begin() + m); 
        //第三次只逆转结尾m个
        reverse(a.begin() + m, a.end()); 
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

48. 旋转图像

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

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

旋转二维矩阵的难点在于将「行」变成「列」，将「列」变成「行」，而只有按照对角线的对称操作是可以轻松完成这一点的，对称操作之后就很容易发现规律了。

我们可以先将 n x n 矩阵 matrix 按照左上到右下的对角线进行镜像对称：

然后再对矩阵的每一行进行反转：

发现结果就是 matrix 顺时针旋转 90 度的结果：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for(int i = 0; i < n; i++){
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

那如何将矩阵逆时针旋转 90 度呢？

思路是类似的，只要通过另一条对角线镜像对称矩阵，然后再反转每一行，就得到了逆时针旋转矩阵的结果：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n - i; j++){
                swap(matrix[i][j], matrix[n - j - 1][n - i - 1]);
            }
        }
        for(int i = 0; i < n; i++){
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

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

解题的核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界。

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

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int upper = 0, lower = m - 1, left = 0, right = n - 1;
        vector<int> res;
        // res.size() == m * n 则遍历完整个数组
        while(res.size() < m * n){
            // 在顶部从左向右遍历
            if(upper <= lower){
                for(int j = left; j <= right; j++){
                    res.push_back(matrix[upper][j]);
                }
                // 上边界下移
                upper++;
            }
            if(left <= right){
                // 在右侧从上向下遍历
                for(int i = upper; i <= lower; i++){
                    res.push_back(matrix[i][right]);
                }
                // 右边界左移
                right--;
            }
            if(upper <= lower){
                // 在底部从右向左遍历
                for(int j = right; j >= left; j--){
                    res.push_back(matrix[lower][j]);
                }
                // 下边界上移
                lower--;
            }
            if(left <= right){
                // 在左侧从下向上遍历
                for(int i = lower; i >= upper; i--){
                    res.push_back(matrix[i][left]);
                }
                // 左边界右移
                left++;
            }
        }
        return res;
    }
};
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

59. 螺旋矩阵II

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

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

和上一道题类似的思路：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int upper = 0, lower = n - 1, left = 0, right = n - 1;
        int num = 1;
        while(num <= n * n){
            if(upper <= lower){
                for(int j = left; j <= right; j++){
                    res[upper][j] = num++;
                }
                upper++;
            }
            if(left <= right){
                for(int i = upper; i <= lower; i++){
                    res[i][right] = num++;
                }
                right--;
            }
            if(upper <= lower){
                for(int j = right; j >= left; j--){
                    res[lower][j] = num++;
                }
                lower--;
            }
            if(left <= right){
                for(int i = lower; i >= upper; i--){
                    res[i][left] = num++;
                }
                left++;
            }
        }
        return res;
    }
};
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

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。

输入：nums = [10,2]
输出："210"
1
2

此题求拼接起来的最小数字，本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y，则规定排序判断规则为：若拼接字符串x + y > y + x，则x“大于”y；反之，若x + y < y + x，则x"小于”y。x“小于”y代表：排序完成后，数组中x应在y左边；“大于”则反之。根据以上规则，套用任何排序方法对nums执行排序即可。

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> strs;
        string res;
        for(int num : nums){
            strs.push_back(to_string(num));
        }
        sort(strs.begin(), strs.end(), [&](string a, string b){
            return a + b > b + a;
        });
        for(string str : strs){
            res += str;
        }
        //避免全部为0的情形
        return res[0] == '0' ? "0" : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积，即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
1
2

分别迭代计算下三角和上三角两部分的乘积，再相乘，即可 不使用除法 就获得结果。

class Solution{
public:
    vector<int> constructArr(vector<int> &a){
        vector<int> res(a.size(), 1);
        int left = 1;	// 左侧乘积
        int right = 1;	// 右侧乘积
        for (int i = 0; i < a.size(); ++i){
            //左侧的乘积
            res[i] *= left; 
            left *= a[i];
            //右侧的乘积
            res[a.size() - 1 - i] *= right; 
            right *= a[a.size() - 1 - i];
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

66. 加一

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

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
1
2
3

其实就是一个数的各位储存在数组里，然后要按照整数加法的法则来计算，然后同样返回一个数组：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int len = digits.size();
        for(int i = len - 1; i >= 0; i --){
            digits[i] ++;
            digits[i] %= 10;
            if(digits[i] != 0){
                return digits;
            }
        }
        digits = vector<int>(len + 1);
        digits[0] = 1;
        return digits;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

杨辉三角

118. 杨辉三角

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行，在「杨辉三角」中，每个数是它左上方和右上方的数的和。

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
1
2

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        for (int i = 0; i < numRows; ++i) {
            res[i].resize(i + 1);
            res[i][0] = res[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

119. 杨辉三角 II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

输入: rowIndex = 3
输出: [1,3,3,1]
1
2

由于只要输出指定的某一行，故只需保存当前行的前一行结果即可。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        if(rowIndex == 0) return {1};
        if(rowIndex == 1) return {1, 1};
        vector<int> res(2, 1);
        for(int i = 2; i <= rowIndex; i++){
            vector<int> tmp(i + 1, 1);
            for(int j = 1; j < i; j++){
                tmp[j] = res[j - 1] + res[j];
            }
            swap(res, tmp);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

870. 优势洗牌（田忌赛马）

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]
1
2

田忌赛马算法实现。比得过最弱的，则正常放置；比不过，则用来消耗最强的。

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> idx(n), res(n);
        // 给数组递增赋值
        iota(idx.begin(), idx.end(), 0);
        // 按照nums2的顺序给idx排序
        sort(idx.begin(), idx.end(), [&](int i, int j){
            return nums2[i] < nums2[j];
        });
        sort(nums1.begin(), nums1.end());
        int left = 0, right = n - 1;
        for(int i = 0; i < n; i++){
            if(nums1[i] > nums2[idx[left]]){
                // 比得过最小的，则正常放置
                res[idx[left]] = nums1[i];
                left++;
            }else{
                // 比不过最小的，则用来消耗最强的
                res[idx[right]] = nums1[i];
                right--;
            }
        }
        return res;
    }
};
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

索引和数组元素对应

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

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

由于数组中的元素都是正数，且都在1到n 的范围内，故可以使用数组的下标作为辅助。

将和数组元素值相同的数组下标中对应的值置为其对应的负数，这样，当两个相同的元素映射到同一个位置，会发现元素值已经为负数了，既该值为重复的值。由于有映射负数的步骤，故使用数组元素时，需要使用其绝对值。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for(int num : nums){
            if(nums[abs(num)] < 0){
                return abs(num);
            }else{
                nums[abs(num)] *= -1;
            }
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

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

和上一题一样的思路，但是需要注意索引的取值范围。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int num : nums){
            if(nums[abs(num) - 1] < 0){
                res.push_back(abs(num));
            }else{
                nums[abs(num) - 1] *= -1;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

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

nums 中的元素取值都在 [1, n] 之间，即元素本身就和索引成一一映射关系，所以可以用 nums 本身模拟哈希集合的效果。那么最终缺失的那些元素对应的索引就不会被标记，我们也就可以把缺失的那些元素找出来。

注意：用乘 -1 的方式给索引做标记的前提是，nums 中的元素都为正数，不能包含 0，否则无法区分该索引是否被标记。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for(int num : nums){
            // 注意索引，元素大小从 1 开始，有一位索引偏移
            if(nums[abs(num) - 1] < 0) continue; // 索引重复出现
            nums[abs(num) - 1] *= -1; // 把索引 num - 1 置为负数
        }
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > 0){
                // 说明没有元素和这个索引对应，即找到一个缺失元素
                res.push_back(i + 1);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
1
2
3
4
5
6

把所有的数分成了三部分，一部分小于等于 first，中间部分小于等于 second，以及最后的一部分大于second。只要出现了第三部分，就满足条件，返回true；否则，跳出循环后，返回false。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX;
        int second = INT_MAX;
        for(int& num : nums){
            //不停的将后面的数据分成三部分
            if(num <= first){
                //先更新first
                first = num;
            }else if(num <= second){
                //然后才能更新second
                second = num;
            }else if(num > second){
                //则出现大于second的数据时，直接返回true
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

剑指 Offer 51. 数组中的逆序对（难）

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

输入: [7,5,6,4]
输出: 5
1
2

在归并排序过程中会将数组划分成最小为1个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。这里我们也可以用相同的方法划分，划分之后相邻一个元素的子数组就可以根据大小统计逆序对，而不断往上合并的时候，因为已经排好序了，我们逆序对可以往上累计。我们主要有以下三个阶段。

具体做法：

• step 1： 划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
• step 2： 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
• step 3： 合并阶段：将排好序的子序列合并，同时累加逆序对。

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        return mergeSort(0, n - 1, nums, res);
    }

    int mergeSort(int left, int right, vector<int>& nums, vector<int>& tmp){
        // 停止划分
        if(left >= right) return 0;
        // 取中间
        int mid = (left + right) / 2;
        // 左右划分合并
        int res = mergeSort(left, mid, nums, tmp) + mergeSort(mid + 1, right, nums, tmp);
        int i = left, j = mid + 1;
        for(int k = left; k <= right; k++){
            tmp[k] = nums[k];
        }
        for(int k = left; k <= right; k++){
            if(i == mid + 1){
                nums[k] = tmp[j++];
            }else if(j == right + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{ // 左边比右边大，答案增加
                nums[k] = tmp[j++];
                // 统计逆序对
                res += mid - i + 1;
            }
        }
        return res;
    }
};
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