在未排序的数组中搜索总计为一个值的3个元素 [英] Search unsorted array for 3 elements which sum to a value

问题描述

我正在尝试制定Θ(n²)的算法.
它接受 n 个元素的未排序数组以及一个整数 z ，
并且必须返回3个不同元素a，b，c的3个索引；所以a + b + c = z.
(如果找不到这样的整数，则返回NILL)

I am trying to make an algorithm, of Θ( n² ).
It accepts an unsorted array of n elements, and an integer z,
and has to return 3 indices of 3 different elements a,b,c ; so a+b+c = z.
(return NILL if no such integers were found)

我试图先以两种方式对数组进行排序，然后再搜索排序后的数组.
但是由于其余算法需要特定的运行时间，所以我迷路了.
有没有排序的方法吗? (我想它必须要排序)有或没有排序都很好.

I tried to sort the array first, in two ways, and then to search the sorted array.
but since I need a specific running time for the rest of the algorithm, I am getting lost.
Is there any way to do it without sorting? (I guess it does have to be sorted) either with or without sorting would be good.

示例:
对于此数组:1, 3, 4, 2, 6, 7, 9和整数6

example:
for this array : 1, 3, 4, 2, 6, 7, 9 and the integer 6

它必须返回:0, 1, 3

因为(1 + 3 + 2 = 6)

because ( 1+3+2 = 6)

推荐答案

算法

1. 排序-O(nlogn)
2. 对于i = 0 ... n-1-O(1)向i赋值
3. new_z = z-array [i]该值在每次迭代时更新.现在，使用两个指针搜索new_z，分别从开始(索引0)和结束(索引n-1)开始.如果总和(array [ptr_begin] + array [ptr_ens])大于new_z，则从顶部的指针中减去1.如果较小，则加1开始指针.否则，返回i，表示当前的结束位置并开始. -O(n)
4. 跳至第2步-O(1)

步骤2、3和4的成本为O(n ^ 2).总体来说，O(n ^ 2)

Steps 2, 3 and 4 cost O(n^2). Overall, O(n^2)

C ++代码

#include <iostream>
#include <vector>
#include <algorithm>


int main()
{
    std::vector<int> vec = {3, 1, 4, 2, 9, 7, 6};
    std::sort(vec.begin(), vec.end());

    int z = 6;
    int no_success = 1;
    //std::for_each(vec.begin(), vec.end(), [](auto const &it) { std::cout << it << std::endl;});

    for (int i = 0; i < vec.size() && no_success; i++)
    {

        int begin_ptr = 0;
        int end_ptr = vec.size()-1;
        int new_z = z-vec[i];

        while (end_ptr > begin_ptr)
        {
            if(begin_ptr == i)
                begin_ptr++;
            if (end_ptr == i) 
                end_ptr--;

            if ((vec[begin_ptr] + vec[end_ptr]) > new_z)
                end_ptr--;
            else if ((vec[begin_ptr] + vec[end_ptr]) < new_z)
                begin_ptr++;
            else {
                std::cout << "indices are: " << end_ptr << ", " << begin_ptr << ", " << i << std::endl;
                no_success = 0;
                break;
            }
        }
    }
    return 0;
}

当心，结果是排序的索引.您可以维护原始数组，然后搜索与排序后的数组对应的值. (O(n)的3倍)

Beware, result is the sorted indices. You can maintain the original array, and then search for the values corresponding to the sorted array. (3 times O(n))

这篇关于在未排序的数组中搜索总计为一个值的3个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！