子数组、子集和子序列的区别

Question

我对子数组、子序列和子集有点困惑。

如果我有{1,2,3,4}

那么

子序列可以是{1,2,4}或{2,4}等。因此，我可以省略一些元素但保持顺序。

子数组将是（假设大小为3）

{1,2,3}
{2,3,4} 

那么什么是子集呢？

我对这三个有点困惑。

- user2821242

---

子集是一个集合的子集。 - Hot Licks

这不是一个很明显的编程问题。它似乎是一个关于理论计算机科学术语的问题。另外，当你写“如果我有{1, 2, 3, 4}”，那么“{1, 2, 3, 4}”是什么？它是一个数组吗？是一个集合吗？还是一个序列？ - Raymond Chen

我的意思是：假设我有一个整数数组，如果让我找到所有子集和子数组，那么它们是相同的吗？如果不是，子集包括什么，子数组包括什么？在这种情况下会怎样？ - user2821242

Answer 1

考虑一个数组：

 {1,2,3,4}

子数组：指的是一个连续的序列，存在于一个数组中，即

{1,2},{1,2,3}

子序列：不需要连续，但保持顺序，即

{1,2,4}

子集：与子序列相同，只是它包含空集，即

 {1,3},{}

给定大小为n的数组/序列，可能的

Subarray = n*(n+1)/2
Subseqeunce = (2^n) -1 (non-empty subsequences)
Subset = 2^n

- Sandip Pawar

---

然而，子集不需要保持顺序。 - Eduardo Sebastian

Answer 2

依我所见，如果给出的模式是数组，那么所谓的subarray就意味着连续子序列。

例如，如果给定{1, 2, 3, 4}，subarray可以是

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

虽然给定的模式是一个序列，但子序列包含那些在原始序列中下标递增的元素。

例如，在{1、2、3、4}中，子序列可以是

{1, 3}
{1，4}
etc.

虽然给定的模式是一个集合，但是子集包含原始集合的所有可能组合。

例如，{1, 2, 3, 4}的子集可以是：

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

- Wilson

---

你需要提及“子集”不需要保持顺序，也可以为空。 - zeitgeist

Answer 3

考虑在元素的集合（数组、序列、集合等）中的这两个属性：顺序和连续性。

顺序是指不能交换两个或多个元素的索引或位置（单个元素的集合具有无关紧要的顺序）。

连续性是指一个元素必须将其相邻的元素与之保持在一起或为空。

子数组具有顺序和连续性。

子序列具有顺序但没有连续性。

子集既没有顺序也没有连续性。

具有连续性但没有顺序的集合不存在（据我所知）。

- user2361174

Answer 4

在数组的上下文中，SubSequence - 不需要是连续的，但需要保持顺序。但 SubArray 是连续的并固有地保持顺序。

例如有 {1,2,3,4} --- {1,3,4} 是一个有效的 SubSequence 但不是subarray。

而 subset 没有顺序也不连续。所以你 {1,3,2} 是一个有效的子集但不是 subsequence 或者 subarray。

{1,2} 是一个有效的 subarray，subset 和 subsequence。

所有的 Subarrays 都是 subsequences 而且所有的 subsequence 都是 subsets。

但有时候 subset 和 subarrays 和 subsequences 会互相替换使用，这时候会在前面加上连续性来使其更清晰。

- Roma

Answer 5

据我理解，例如我们有一个列表 [3,5,7,8,9]。这里的子集不需要保持顺序，可以是非连续的。例如，[9,3] 是一个子集。

子序列保持顺序并具有非连续行为。例如，[5,8,9] 是一个子序列。

子数组保持顺序并具有连续行为。例如，[8,9] 是一个子数组。

- nillu

Answer 6

简单明了的解释：

子数组：它应该始终是连续的形式。

例如，让我们取一个数组 int arr=[10,20,30,40,50];

-->现在让我们看看它的各种组合：

  subarr=[10,20] //true
  subarr=[10,30] //false, because its not in contiguous form
  subarr=[40,50] //true

子序列：不需要连续形式，但顺序相同。

例如，让我们取一个数组 int arr=[10,20,30,40,50];

-->现在让我们看看它的各种组合：

  subseq=[10,20]; //true
  subseq=[10,30]; //true
  subseq=[30,20]; //false, because order isn't maintained

子集：指任何可能的组合。

例如，我们有一个数组 int arr=[10,20,30,40,50];

-->现在让我们看看它的各种组合：

  subset={10,20}; //true
  subset={10,30}; //true
  subset={30,20}; //true

- Safin Ghoghabori

Answer 7

子数组：数组中一些连续的元素

子集：集合中的一些元素

子序列：通常指数组中保持相对顺序的一些元素（不必连续）

- GraceMeng

Answer 8

以下是数组的示例：

Array : 1,2,3,4,5,6,7,8,9
Sub Array : 2,3,4,5,6 >> Contagious Elements in order
Sub Sequence : 2,4,7,8 >> Elements in order by skipping any or 0 elements
Subset : 9,5,2,1 >> Elements by skipping any or 0 elements but not in order

- Kalpit Sharma

Answer 9

子数组是数组的连续部分，并保持元素的相对顺序。对于大小为n的数组/字符串，总共有n*(n+1)/2个非空子数组/子字符串。

子序列保持元素的相对顺序，但不一定是数组的连续部分。对于大小为n的序列，我们可以总共有2^n-1个非空子序列。

子集不保持元素的相对顺序，也不是数组的连续部分。对于大小为n的集合，我们可以总共有(2^n)个子集。 让我们通过一个例子来理解它。

考虑一个数组：

array = [1,2,3,4]

子数组：[1,2]，[1,2,3] — 连续且保持元素的相对顺序

子序列：[1,2,4] — 不连续但保持元素的相对顺序

子集：[1,3,2] — 不连续且不保持元素的相对顺序

一些有趣的观察结果：

每个子数组都是一个子序列。 每个子序列都是一个子集。

- Twinshu Parmar

Answer 10

Suppose an Array [3,4,6,7,9]

Sub Array is a continuous and ordered part of that array
example is [3,4,6],[7,9],[5]

Sub Sequence has not need to be continuous but they should be in order
example is [3,4,9],[3,7],[6]

Subset neither need to be continuous nor to be in order
Example is [9,4,7],[3,4],[5]

- Abhishek Kansana

---

给定这个例子，子数组[5]和子序列[5]是不可能的。 - undefined