时间戳

首页 > 解决方案 > 计算子序列、子集和子字符串的正确方法是什么？

algorithm - 计算子序列、子集和子字符串的正确方法是什么？

问题描述

我经常在编码面试中遇到以下术语。

给定一个数组或字符串，找到子数组子序列子字符串

他们有什么区别？例如，我看到一个整数数组可以拆分为

n*(n+1)/2

子数组。它们也成为子集吗？子数组应该是连续的吗？对于计算字符串的子序列，为什么要使用

2^str_length - 1

在网上搜索后，我最终得到了这个链接 https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/

但是我仍然感到模棱两可，因为调用数组/字符串的一部分的通用术语是什么？以及如何计算它们？

标签： algorithm

解决方案

一般来说，数组和字符串都是子序列。“序列”部分表明元素的顺序在某种程度上很重要。“子串”通常是连续的；“子阵列”和“子序列”不清楚。如果您在面试中并且不确定解释，那么您的第一项工作就是询问。有时，工作面试的一部分是确保您能够发现并解决模棱两可的问题。

问题更新后更新

我发现引用的页面很清楚。首先，请注意字符串和数组都是序列的特定类型。

  • 子序列是通用术语：原始序列的元素以与原始序列相同的顺序出现，但不一定是连续的。例如，给定序列“abcdefg”，我们有子序列“a”、“ag”、bce”等。
  • 重复或不在原始顺序中的元素将包括“ga”、“bb”、bcfe”等。这些都不是子序列。
  • “子集”是一个单独的类型。在一个集合中，重复的元素不存在，顺序也无关紧要。

这能解决你的问题吗？

推荐阅读