元素小于 k 的子数组数

Question

我在一次采访中有以下问题。
给定一个数组，您需要找到所有元素小于给定值 k
的子数组，例如

if k=4,
arr[]={4,8,2,4,6}

现在值小于 4 的子数组是：

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

请注意{4}是如何重复的，但没有考虑两次。现在，代码应返回不同子数组的计数。
在这种情况下 3.
再比如：

k=4
arr[]={2,3,8,2,4,6}

不同的子数组：

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

我的方法是找到小于给定值 k 的子数组，即 O(n^2)，然后将其插入类似 unordered_set 的内容以删除重复项。

有没有有效的方法来解决这个问题？

Answer 1

因此，在摆弄了几分钟之后，我终于想出了一个解决方案，即使您的结果与我的结果不同，也可以逐字满足您所陈述的内容。在您的问题中，您明确指出：

给定一个数组，找到元素小于给定值 k 的所有不同子数组。

您给出了我在解决方案中使用的以下示例。

k=4
arr[]={2, 3, 8, 2, 4, 6}

你得出的结论是，结果应该是：

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

实际上，如果您的需求真正得到满足，您将只有三个不同的数组，因为这些元素必须小于k提供的值，在本例中4：

The values are: 2,3,8,2,4,6
Distinct Arrays Are: {2} {3} {2,3}

---

解决方案(在 C# 6.0 中)

随意在.NET Fiddle(需要调整到C# 4.5)或Visual Studio(当前处理C# 6.0)中对此进行测试。如果这是您最终需要的，我不确定如何将其翻译回您的数学公式，但是根据所需结果的描述，此解决方案有效。

using System;
using System.Collections.Generic;
public class Program {
static int k = 4;
static int[] vals = new int[]{ 2, 3, 8, 2, 4, 6 };
static List<string> distinctVals = new List<string>();
public static void Main() {
Console.WriteLine($"The values are: {string.Join(",", vals)}");
for (int x = 0; x < vals.Length; x++) {
if (vals[x] < k)
if (!distinctVals.Contains(vals[x].ToString()))
distinctVals.Add(vals[x].ToString());
for (int y = 0; y < vals.Length; y++) {
if (vals[y] < k) {
if (!distinctVals.Contains(vals[y].ToString()))
distinctVals.Add(vals[y].ToString());
if (vals[x] < k && vals[x] != vals[y])
if (!distinctVals.Contains($"{vals[x]},{vals[y]}"))
if (!distinctVals.Contains($"{vals[y]},{vals[x]}"))
distinctVals.Add($"{vals[x]},{vals[y]}");
}
}
}
Console.WriteLine($"There are {distinctVals.Count} distinct array elements.");
Console.Write($"The distinct elements are: {{{string.Join("}; {", distinctVals)}}};");
}
}