给定一个未排序阵列，查找其总和等于由用户输入的总和的阵列中的任何两个元素 [英] Given an unsorted array, find any two elements in the array whose sum is equal to the sum entered by the user

问题描述

一个）给定一个未排序的阵列，查找其总和等于一个号码由用户输入阵列中的任何两个元素

A) Given an unsorted array, find any two elements in the array whose sum is equal to a number entered by the user.

B）该程序应使用不超过超出所需阵列本身常数存储更多。

B) The procedure should use no more than constant storage beyond that needed for the array itself.

我们能找到的运行时间一个解决方案，具有O（n）的最坏情况？

Can we find a solution which has O(n) worst-case running time?

推荐答案

我觉得下面的想法应该工作：

I think the following idea should work:

1. Sort the input array, call it a[]
2. Maintain a pointer to the front and back of the array, i and j
3. While a[i] + a[j] != sum and i != j
4.     Move the pointers toward the middle appropriately based on whether
       a[i] + a[j] > sum or a[i] + a[j] < sum
5. Return False if (i == j) or a[i] and a[j] otherwise

这个成本 O（nlgn），因为你需要做的（就地）排序的数组。如果你的数组已经排序，那么这种算法的成本降低到 O（N）。

This costs O(nlgn) because you need to do an (in-place) sort of the array. If your array is already sorted, then the cost of this algorithm decreases to O(n).

这篇关于给定一个未排序阵列，查找其总和等于由用户输入的总和的阵列中的任何两个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！