元素小于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））的子阵列，然后将其插入类似无序集的内容中以删除重复项。

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

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)}}};");
    }
}