2

Here's the statement of the problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

If nums is an array of integers there are 2 possible solutions:

  1. Check that compliment exists in hash table, otherwise insert in hash table.
  2. Sort and traverse from both ends using two pointers.

How can I solve this question if the nums is an array of doubles?

Alex Pivovar
  • 29
  • 1
  • For method #2, you could use a tolerance. If you need `c = a + b` for two numbers `a` and `b` in the array, you could instead check `abs(c - a + b) <= tolerance`. Method #1 might be reworked to use a BST (or similar), and check if a value exists that is close enough to make the equality work (within tolerance). But in general: you should [not rely on exact comparisons between doubles](https://stackoverflow.com/questions/7180952/is-checking-a-double-for-equality-ever-safe), and instead allow for a small tolerance. – Nelewout Apr 19 '20 at 11:17
  • @N.Wouda, if you downvoted my answer, I must tell you the question was only about algorithm. – Deepak Tatyaji Ahire Apr 19 '20 at 11:18
  • Checking for double equality is part of programming constructs – Deepak Tatyaji Ahire Apr 19 '20 at 11:19
  • Instead you have improved my answer :( – Deepak Tatyaji Ahire Apr 19 '20 at 11:22
  • Related: https://stackoverflow.com/questions/50848128/determine-if-any-combinations-of-doubles-from-a-set-sum-to-target-value – mic Oct 17 '20 at 21:19

1 Answers1

-1

The same way as you solved it for integers.

Also, correctly pointed out by @Nelewout that the elements of type double will require a special equality comparison, but still the algorithm remains the same.

Deepak Tatyaji Ahire
  • 4,883
  • 2
  • 13
  • 35
  • 1
    At some point in the algorithm, this'd require an equality comparison between two doubles. For method #1, that's implicit, for #2 it's not. But direct equality between doubles is.. [problematic](https://stackoverflow.com/questions/7180952/is-checking-a-double-for-equality-ever-safe). – Nelewout Apr 19 '20 at 11:14
  • Correct, but the algorithm remains the same – Deepak Tatyaji Ahire Apr 19 '20 at 11:16
  • Interesting, any ideas how I can do it using a hashtable (i.e. time: O(N), memory: O(N))? – Alex Pivovar Apr 19 '20 at 17:09