在给定的一组数字中找出3的可能算术级数 [英] Finding the number of possible arithmetic series of 3 among a given set of numbers

问题描述

给定一个整数，问题在于查找长度为3的可能算术级数。整数集可以排序也可以不排序。

Given a set integers, the problem consists of finding the number of possible arithmetic series of length 3. The set of integers may or may not be sorted.

I可以实现耗时O（n ^ 3）的简单蛮力算法，但是时间效率很重要，并且整数集可以高达10 ^ 5。这意味着暴力破解显然行不通。有人可以在c ++中建议一些算法/伪代码/代码吗？

I could implement a simple bruteforce algorithm taking time O(n^3) but time efficiency is important and the set of integers can be as large as 10^5. This means bruteforce obviously won't work. Can anyone suggest some algorithm/pseudocode/code in c++?

示例：有4个数字5,2,7,8。显然，只有这样一种可能性-（2,5,8），其中共同的差是3，所以我们的答案是1。

An example: there are 4 numbers 5,2,7,8 . Clearly there is only one such possibility - (2,5,8) in which the common difference is 3, so our answer is 1.

编辑：我忘了提到一个重要的属性-给定的每个集合数在1到30000（含1和30000）之间。

EDIT:I forgot to mention one important property - each number of set given is between 1 to 30000 (inclusive).

推荐答案

您可以在O（N ^ 2）中执行以下操作：创建整数的哈希集，以便可以检查 O（1）。之后，在所有对设置元素 {X，Y} 上进行两个嵌套循环。这是在 O（N ^ 2）中完成的。

You can do it in O(N^2) as follows: create a hash set of your integers so that you could check a presence or absence of an element in O(1). After that, make two nested loops over all pairs of set elements {X, Y}. This is done in O(N^2).

对于每对 {X ，Y} ，假设 X< Y ，并计算两个数字：

For each pair {X, Y}, assume that X < Y, and calculate two numbers:

Z1 = X - (Y-X)
Z2 = Y + (Y-X)

三元组 {X，Y，Zi} 构成一个算术序列，如果 Zi！= X& Zi！= Y&& set.contains（Zi）

A triple {X, Y, Zi} form an arithmetic sequence if Zi != X && Zi != Y && set.contains(Zi)

检查两个三元组 {X，Y，Z1} 和 {X，Y，Z2} 。您可以使用哈希集在 O（1）中进行操作，算法的总运行时间为 O（N ^ 2）。

Check both triples {X, Y, Z1} and {X, Y, Z2}. You can do it in O(1) using a hash set, for a total running time of the algorithm of O(N^2).

这篇关于在给定的一组数字中找出3的可能算术级数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！