1. 1. 面试算法高频总结：子数组和子序列到底有什么区别？
    1. 1.1. 目录
    2. 1.2. 一、先说结论
    3. 1.3. 二、什么是子数组？
    4. 1.4. 三、什么是子序列？
    5. 1.5. 四、字符串里的“子串”和“子序列”
      1. 1.5.1. 1）子串（Substring）
      2. 1.5.2. 2）子序列（Subsequence）
    6. 1.6. 五、子数组和子序列的本质区别
      1. 1.6.1. 1）子数组：连续区间问题
      2. 1.6.2. 2）子序列：选或不选问题
    7. 1.7. 六、最容易混淆的地方
      1. 1.7.1. 1）子数组一定是子序列，但子序列不一定是子数组
      2. 1.7.2. 2）子串一定是子序列，但子序列不一定是子串
      3. 1.7.3. 3）子集又是另一个概念
    8. 1.8. 七、怎么快速判断一道题是子数组还是子序列？
    9. 1.9. 八、子数组常见题型与做法
      1. 1.9.1. 1）最大子数组和
        1. 1.9.1.1. 题意
        2. 1.9.1.2. 典型做法
        3. 1.9.1.3. 为什么？
        4. 1.9.1.4. 核心状态
        5. 1.9.1.5. 标准代码
      2. 1.9.2. 2）和为 K 的子数组
        1. 1.9.2.1. 题意
        2. 1.9.2.2. 典型做法
        3. 1.9.2.3. 为什么？
        4. 1.9.2.4. 核心思想
        5. 1.9.2.5. 标准代码
      3. 1.9.3. 3）长度最小的子数组
        1. 1.9.3.1. 题意
        2. 1.9.3.2. 典型做法
        3. 1.9.3.3. 为什么？
        4. 1.9.3.4. 标准代码
      4. 1.9.4. 4）乘积小于 K 的子数组
        1. 1.9.4.1. 题意
        2. 1.9.4.2. 典型做法
        3. 1.9.4.3. 为什么？
        4. 1.9.4.4. 核心技巧
        5. 1.9.4.5. 标准代码
    10. 1.10. 九、子序列常见题型与做法
      1. 1.10.1. 1）判断 s 是否是 t 的子序列
        1. 1.10.1.1. 题意
        2. 1.10.1.2. 典型做法
        3. 1.10.1.3. 核心思想
        4. 1.10.1.4. 标准代码
      2. 1.10.2. 2）最长公共子序列 LCS
        1. 1.10.2.1. 题意
        2. 1.10.2.2. 典型做法
        3. 1.10.2.3. 状态定义
        4. 1.10.2.4. 转移
        5. 1.10.2.5. 标准代码
      3. 1.10.3. 3）最长递增子序列 LIS
        1. 1.10.3.1. 题意
      4. 1.10.4. 做法一：动态规划
        1. 1.10.4.1. 标准代码
      5. 1.10.5. 做法二：贪心 + 二分
      6. 1.10.6. 4）不同的子序列
        1. 1.10.6.1. 题意
        2. 1.10.6.2. 典型做法
        3. 1.10.6.3. 状态定义
        4. 1.10.6.4. 转移
        5. 1.10.6.5. 初始化
        6. 1.10.6.6. 标准代码
    11. 1.11. 十、为什么同样是“子数组题”，方法也不一样？
      1. 1.11.1. 1）如果数组元素全是正数
      2. 1.11.2. 2）如果数组里可能有负数
    12. 1.12. 十一、为什么同样是“子序列题”，方法也不一样？
      1. 1.12.1. 1）判断能不能匹配
      2. 1.12.2. 2）求最长
      3. 1.12.3. 3）求方案数
    13. 1.13. 十二、面试里最容易踩的坑
      1. 1.13.1. 1）“最长公共子串”和“最长公共子序列”不是一个题
        1. 1.13.1.1. 最长公共子串
        2. 1.13.1.2. 最长公共子序列
      2. 1.13.2. 2）“最长递增子序列”和“最长连续递增序列”不是一个题
        1. 1.13.2.1. 最长递增子序列
        2. 1.13.2.2. 最长连续递增序列
      3. 1.13.3. 3）看到“连续”两个字就要敏感
    14. 1.14. 十三、面试里的快速判断模板
      1. 1.14.1. 1）要求连续吗？
      2. 1.14.2. 2）元素能不能有负数？
      3. 1.14.3. 3）题目求什么？
    15. 1.15. 十四、总表总结
      1. 1.15.1. 1）子数组 / 子串
      2. 1.15.2. 2）子序列
    16. 1.16. 十五、最后总结
      1. 1.16.1. 子数组 / 子串
      2. 1.16.2. 子序列
    17. 1.17. 附：一段适合放在结尾的总结话术

子数组和子序列

c++ › 随笔

面试算法高频总结：子数组和子序列到底有什么区别？

刷算法题时，很多人都会被这几个概念绕晕：子数组、子串、子序列、子集。
它们名字很像，但定义、做法、题型特征都不一样。
如果一开始没分清，后面做题很容易方向跑偏。
这篇文章就系统总结一下：子数组和子序列到底有什么区别，它们常见的题型分别怎么做。

目录

一、先说结论

最核心的一句话：

  • 子数组 / 子串：必须连续
  • 子序列：可以不连续，但必须保持相对顺序

这是区分它们的根本标准。

二、什么是子数组？

子数组（Subarray）是指：

从原数组中选出一个连续区间。

比如数组：

1
[1, 2, 3, 4]

它的子数组有：

1
2
3
4
5
6
7
8
9
10
[1]
[2]
[3]
[4]
[1,2]
[2,3]
[3,4]
[1,2,3]
[2,3,4]
[1,2,3,4]

但下面这些不是子数组：

1
2
3
[1,3]
[1,4]
[2,4]

因为它们不连续。

三、什么是子序列？

子序列（Subsequence）是指：

从原数组中按顺序选出若干元素，可以跳过一些元素，但不能改变原来的相对顺序。

还是这个数组：

1
[1, 2, 3, 4]

它的子序列可以有：

1
2
3
4
5
6
7
8
9
10
[1]
[2]
[3]
[4]
[1,2]
[1,3]
[1,4]
[2,4]
[1,3,4]
[1,2,4]

但是：

1
[3,2]

不是子序列，因为顺序变了。

四、字符串里的“子串”和“子序列”

例如字符串：

1
"abcde"

1）子串（Substring）

必须连续，比如：

1
2
3
4
"a"
"ab"
"bcd"
"cde"

"ace" 不是子串，因为不连续。

2）子序列（Subsequence）

可以跳过，比如：

1
2
"ace"
"abd"

但 "aec" 不是子序列，因为顺序错了。

五、子数组和子序列的本质区别

1）子数组：连续区间问题

子数组的本质是：

选一个左端点和一个右端点，中间整段都要拿。

所以很多子数组题都和下面这些方法有关：

  • 滑动窗口
  • 双指针
  • 前缀和
  • 单调队列
  • 单调栈
  • Kadane 动态规划

2）子序列：选或不选问题

子序列的本质是：

每个位置都要考虑，这个元素要不要选。

所以很多子序列题都和下面这些方法有关：

  • 动态规划
  • 双指针
  • 贪心
  • 贪心 + 二分

六、最容易混淆的地方

1）子数组一定是子序列，但子序列不一定是子数组

例如：

1
[1,2,3,4]
  • [2,3]：既是子数组，也是子序列
  • [1,3]：是子序列，但不是子数组

所以可以这样理解：

子数组是“更严格”的子序列。

2）子串一定是子序列，但子序列不一定是子串

例如：

1
"abcde"
  • "bcd"：既是子串，也是子序列
  • "ace"：是子序列，但不是子串

3）子集又是另一个概念

子集（subset）通常不强调顺序，只强调“选了哪些元素”。

例如集合 {1,2,3} 的子集有：

1
2
3
4
5
{}
{1}
{2}
{1,3}
...

但子序列要求顺序不能乱。

所以：

  • 子集：选哪些
  • 子序列：按原顺序选哪些
  • 子数组：连续选一段

七、怎么快速判断一道题是子数组还是子序列？

看到题目时，先问自己一句：

答案里的元素，能不能跳过中间元素？

  • 能跳过：大概率是子序列
  • 不能跳过：大概率是子数组 / 子串

八、子数组常见题型与做法

1）最大子数组和

题意

找一个连续子数组，使得和最大。

典型做法

动态规划 / Kadane 算法

为什么？

因为数组里通常可能有负数，不能直接用滑动窗口。

核心状态

定义：

1
dp[i] = 以 nums[i] 结尾的最大子数组和

转移：

1
dp[i] = max(nums[i], dp[i-1] + nums[i])

标准代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            cur = max(nums[i], cur + nums[i]);
            ans = max(ans, cur);
        }
        return ans;
    }
};

2）和为 K 的子数组

题意

求有多少个连续子数组，它们的和等于 k。

典型做法

前缀和 + 哈希表

为什么？

因为数组里可能有负数，滑动窗口不稳定。

核心思想

如果当前前缀和是 sum，想找和为 k 的子数组，就要看之前是否出现过：

1
sum - k

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int sum = 0, ans = 0;

        for (int x : nums) {
            sum += x;
            if (mp.count(sum - k)) ans += mp[sum - k];
            mp[sum]++;
        }
        return ans;
    }
};

3）长度最小的子数组

题意

找和大于等于 target 的最短连续子数组长度。

典型做法

滑动窗口 / 双指针

为什么？

因为题目通常限定数组元素都是正数，此时区间和有单调性。

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, sum = 0, ans = INT_MAX;

        for (int right = 0; right < nums.size(); right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

4）乘积小于 K 的子数组

题意

求乘积小于 k 的连续子数组个数。

典型做法

滑动窗口

为什么？

数组元素通常为正数，窗口扩张时乘积单调变化。

核心技巧

当右端点固定时，如果当前窗口合法，那么以这个右端点结尾的合法子数组个数就是：

1
right - left + 1

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;

        int left = 0;
        int product = 1;
        int ans = 0;

        for (int right = 0; right < nums.size(); right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left++];
            }
            ans += right - left + 1;
        }

        return ans;
    }
};

九、子序列常见题型与做法

1）判断 s 是否是 t 的子序列

题意

判断 s 能不能通过删除 t 中一些字符得到。

典型做法

双指针

核心思想

  • i 扫描 s
  • j 扫描 t
  • 遇到相同字符就让 i++
  • 最后看 i 是否扫完整个 s

标准代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        while (i < s.size() && j < t.size()) {
            if (s[i] == t[j]) i++;
            j++;
        }
        return i == s.size();
    }
};

2）最长公共子序列 LCS

题意

求两个字符串的最长公共子序列长度。

典型做法

二维动态规划

状态定义

1
dp[i][j] = text1前i个字符 和 text2前j个字符 的最长公共子序列长度

转移

如果当前字符相等：

1
dp[i][j] = dp[i-1][j-1] + 1

如果不等：

1
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][m];
    }
};

3）最长递增子序列 LIS

题意

找数组中的最长严格递增子序列长度。

做法一：动态规划

定义：

1
dp[i] = 以 nums[i] 结尾的最长递增子序列长度

转移：

1
dp[i] = max(dp[j] + 1), 其中 j < i 且 nums[j] < nums[i]

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ans = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

做法二：贪心 + 二分

维护一个 tails 数组，表示不同长度递增子序列的最小结尾值。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        return tails.size();
    }
};

4）不同的子序列

题意

问 s 的子序列中，有多少种不同方式可以构成 t。

典型做法

二维动态规划

状态定义

1
dp[i][j] = s的前i个字符中，构成t的前j个字符的方案数

转移

如果当前字符相等：

1
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

解释：

  • 用当前字符匹配
  • 不用当前字符匹配

如果不相等：

1
dp[i][j] = dp[i-1][j]

初始化

1
dp[i][0] = 1

因为构造空串永远只有一种方法：什么都不选。

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(m + 1, 0));

        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return (int)dp[n][m];
    }
};

十、为什么同样是“子数组题”，方法也不一样？

很多人会问：

既然都是子数组，为什么有的用滑动窗口，有的用前缀和，有的用 DP？

关键在于：题目条件不同。

1）如果数组元素全是正数

通常优先考虑：

  • 滑动窗口
  • 双指针

因为区间和、区间积通常具备单调性。

代表题：

  • 长度最小的子数组
  • 乘积小于 K 的子数组

2）如果数组里可能有负数

通常要警惕：

  • 滑动窗口可能失效

这时候更常考虑：

  • 前缀和
  • 哈希表
  • 动态规划

代表题：

  • 最大子数组和
  • 和为 K 的子数组

十一、为什么同样是“子序列题”，方法也不一样？

关键要先看题目在问什么。

1）判断能不能匹配

通常用：

  • 双指针

代表题：

  • 判断 s 是否是 t 的子序列

2）求最长

通常用：

  • 动态规划
  • 或贪心 + 二分优化

代表题：

  • LIS
  • LCS

3）求方案数

通常用：

  • 动态规划

代表题：

  • 不同的子序列

十二、面试里最容易踩的坑

1）“最长公共子串”和“最长公共子序列”不是一个题

最长公共子串

要求连续。

最长公共子序列

不要求连续。

这两个名字只差两个字，但做法完全不同。

2）“最长递增子序列”和“最长连续递增序列”不是一个题

最长递增子序列

不要求连续。

最长连续递增序列

必须连续。

一个是子序列问题，一个更像子数组问题。

3）看到“连续”两个字就要敏感

很多题解法差别就差在这两个字：

  • 连续 → 子数组 / 子串
  • 不连续但顺序不变 → 子序列

十三、面试里的快速判断模板

看到一道题时，先问自己这 3 个问题：

1）要求连续吗？

  • 要求连续 → 子数组 / 子串
  • 不要求连续 → 子序列

2）元素能不能有负数？

  • 有负数 → 滑窗要小心
  • 全正数 → 优先想滑窗

3）题目求什么？

  • 求是否存在 → 双指针 / 前缀和
  • 求最值 → DP / 滑窗 / 贪心
  • 求个数 / 方案数 → 前缀和哈希 / DP

十四、总表总结

1）子数组 / 子串

类型 特点 常见做法
子数组 / 子串 必须连续 滑动窗口、前缀和、双指针、DP

常见题：

题目 方法
最大子数组和 DP / Kadane
和为 K 的子数组 前缀和 + 哈希
长度最小的子数组 滑动窗口
乘积小于 K 的子数组 滑动窗口

2）子序列

类型 特点 常见做法
子序列 可不连续，但顺序不能变 DP、双指针、贪心 + 二分

常见题：

题目 方法
判断 s 是否是 t 的子序列 双指针
最长公共子序列 LCS 二维 DP
最长递增子序列 LIS 一维 DP / 贪心 + 二分
不同的子序列 二维 DP

十五、最后总结

子数组和子序列看起来只差几个字，但它们本质上代表的是两类完全不同的问题。

子数组 / 子串

关注的是：

一个连续区间。

所以常见方法是：

  • 滑动窗口
  • 前缀和
  • 双指针
  • 区间 DP / Kadane

子序列

关注的是：

按原顺序选一些元素。

所以常见方法是：

  • 动态规划
  • 双指针
  • 贪心 + 二分

如果用一句话总结：

连续就想子数组，不连续但顺序不变就想子序列。

这句话几乎能帮你在面试里快速判断大部分题目的方向。

附：一段适合放在结尾的总结话术

很多算法题一眼看上去差不多，但如果先把“连续”和“是否允许跳过元素”这两个问题想清楚，思路会立刻明朗很多。

  • 连续区间问题，优先往子数组方向想；
  • 可以跳过但顺序不能乱，优先往子序列方向想。

真正把这两个概念吃透之后，滑动窗口、前缀和、动态规划这些方法也会更容易找到切入点。