This can be solved efficiently via using HashTables.

We can have a hashtable sums

Thanks.

We can have a hashtable sums

`sums`

will store all possible sums of two different elements. For each sum `S`

it returns pair of indexes `i`

and `j`

such that `a[i] + a[j] == S`

and `i != j`

. But initially it's empty, we'll populate it on the way. So, this can be done in O(n^2) time.**Pseudocode**for (int i = 0; i < n; ++i) { // 'sums' hastable holds all possible sums a[k] + a[l] // where k and l are both less than i for (int j = i + 1; j < n; ++j) { int current = a[i] + a[j]; int rest = X - current; // Now we need to find if there're different numbers k and l // such that a[k] + a[l] == rest and k < i and l < i // but we have 'sums' hashtable prepared for that if (sums[rest] != null) { // found it } } // now let's put in 'sums' hashtable all possible sums // a[i] + a[k] where k < i for (int k = 0; k < i; ++k) { sums[a[i] + a[k]] = pair(i, k); } }

Thanks.

## 0 comments:

## Post a Comment