You may use C++ bitset. It requires O(Max / 8) bytes for space.
If the array is sorted, there is O(n) solution with O(1) space
complexity:
keep two pointers, left = 0 and right = n - 1;
while (l < r) {
int diff = A[l] + A[r] - m;
if (diff > 0) --r;
else if (A[l] + A[r] < 0) ++l;
else break; // found solution
}
// check pointers
if (l != r) then you found solution, so A[l] + A[r] == m
On 22 окт, 15:32, RIDER <[email protected]> wrote:
> you have an array of n integers, how would you find the integer pairs
> which sum to m? complexity?
>
> if we use hash table then should we implement efficient hash table in c
> ++?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
