使用JavaScript查找o（n）时间一维数组中的所有子数组 [英] find all subarrays in o(n) time 1D array using javascript

问题描述

我想收集所有子数组，以便在javascript中有效地进行进一步计算。我不确定这是否可行，但似乎对于子数组求和，kadane的公式为o（n），它比其他方法更有效。但是我不确定如何在每个步骤中存储数组。

I want to collect all subarrays for further computation efficiently in javascript. I'm not sure this is possible, but it seems for a subarray sum kadane's formula is o(n) which is more efficient than other methods. But I'm not sure I how I can store the array at each step.

类似于此 quora问题，对我来说代码还不够。感谢您进一步细分。

Similar to this quora question, for me the pseudo code was not enough. Thanks for the further breakdown.

另一个元链接

[3、3、9、9、5]的操作示例

an example in action of this for [3, 3, 9, 9, 5]

[3], [9], [5], [9, 5], [9, 3], [9, 9], [3, 3],
[3, 9, 9], [3, 3, 9], [9, 9, 5], [3, 3, 9, 9],
[3, 9, 9, 5], [3, 3, 9, 9, 5]

推荐答案

这非常简单： https://jsfiddle.net/j1LuvxLq/

您要做的就是迭代可能的长度和起点，然后仅打印出子集。复杂度为O（n²），其中n是原始数组的长度。没办法改善它，因为那是有多少个子集的顺序。

All you do is iterate possible lenghts and starting points and just print out the subsets. Complexity is O(n²) where n is the length of the original array. No way to improve it thought because that's the order of how many subsets there are.

var set = [3, 3, 9, 9, 5].join('')

var set_length = set.length

var subsets = []

for (var length_of_subset = 1; length_of_subset <= set_length; length_of_subset++) {
    for (var start_of_subset = 0; start_of_subset <= set_length - length_of_subset; start_of_subset++) {
        var current_subset = set.substring(start_of_subset, start_of_subset + length_of_subset)
        if(subsets.indexOf(current_subset) == -1) {
            subsets.push(current_subset.split(''))
        }
    }
}

// print the subsets out
for (s in subsets) {
    $('body').append(subsets[s].join(', ') + '<br>')
}

可能的替代解决方案是使用动态编程。从3开始，然后删除最后一个元素或添加下一个元素。在此处查看： https://jsfiddle.net/p82fcs4m/

Alternative, possibly nicer solution would be to use dynamic programming. Start with 3 and either remove last element or add next element. Check it out here: https://jsfiddle.net/p82fcs4m/

var set = [3, 3, 9, 9, 5].join('')
var subsets = []

take(set[0], set.substring(1))

function take(chosen, left) {

    if(subsets.indexOf(chosen) != -1) {
        return
    }

    subsets.push(chosen)

    if (chosen.length > 1) {
        take(chosen.substring(1), left)
    }

    if (left.length > 0) {
        take(chosen.concat(left[0]), left.substring(1))
    }
}

$('body').append(subsets.join('<br>'))

这篇关于使用JavaScript查找o（n）时间一维数组中的所有子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！