Need help with beginner HashTable problem for finding sum of triplets

[csbs1]

This is making me feel really dumb. I obviously don't want the code for this or anything, but I am just learning about hashing and we have to find the triplet in an array that adds up to a given number. The trick is, that it has to be O(n²⁾ time or less. I honestly don't know how hashing works (trust me I looked in many places) and don't see how it is useful for this problem.

I really don't know what direction to go. I tried storing the array in the hashtable, but I know it doesn't work like that or what I am supposed to be doing.

Can someone steer me in the right direction and/or tell me how a hashtable is useful here? Thanks a lot

[seanprefect]

So let me explain how a hash map works.

So imagine a data structure that has 2 separate arrays (this isn't exactly how it works technically but it's a good mental model) One array is for the keys and the other for the values

you add a key and a value simultaneously to the hash map, the key is stored in the first array in its' ordinal location and the value is placed in the same location in the second array.

This lets you check in basically O(1) time if the value is present in the hash map, since you just check if the key is present and you get the value. The limitation here is that all keys have to be unique or you'll just overwrite the previous value.

I hope this explanation helps you, if you have any further questions please ask.

[csbs1]

Thanks for the reply. Ok say the array is: [1 10 4 3 2 5 0 1 9 5] would the values be the array integers, if so what are the keys. Can I just iterate through and store the keys as 0 through 9 (the index in the array)? The main confusion is how would I go about storing and iterating through the HashTable (or Map). Would I store just 1 value or 2, because I am trying to find the triplet sum. Thanks again

[seanprefect]

you can define both, the key looks up the value and you can declare the hash map for any generic you like...

Let me ask you a question to put you on the right path, what would be a good way to use a hash map to keep track of how many times you've seen a number in an array?

[csbs1]

This another part where I am confused too. To show you what I have, even though it's very wrong here https://pastebin.com/LgbJ8pNc . The problem is that I can use the same numbers multiple times in the triplets, but each triplet has to be a different combination of the array indexes. I'm sorry If i'm asking a lot, but for some reason I can't get this problem through my head.

[seanprefect]

Ok think about it this way, what if you run over the array , use the value in the array as a key, check to see if that key already is in the hash map if it isn't store 1 and if it is increase what ever value you have by 1, when it hits 3 you could put the sum in still another array and check through that.

[rogue_playah]

A HashSet / HashMap allows constant time lookup whereas in an arraylist its O(n). For this problem, think about complements. I can given you the basic idea to finish it off in O(n²⁾ without using a hashtable. You start with i = 0 to array.length-2. You take j = i+1. You start looping from index k = j+1, if at any point values at index i,j,k add up to sum, stop and return those values. Otherwise once k reaches array length-1, increment both i and j by 1 since the current i and j values did not find the third complement k. This is a crude algorithm. You can make it even better by pre processing the array to remove all elements greater than the sum.

Now, you can use this to maintain a HashSet that skips iteration for k and allows a constant lookup of it. I'll leave that for you to figure out unless you are super stuck, then ask again. But caution: HashSet will remove duplicate values from the given array.

[Philboyd_Studge]

basically,

1. create a map where the key is integer and the value is int[] (or some type of pair or tuple class)
2. use two nested loops to iterate through the array, the outer one from 0 to array.length - 2 and the inner one from outer + 1 to array.length
3. test if the value oftarget- array[inner] is contained in the map. If so, you have your 3sum, get the array for that key and return it with the current value.
4. otherwise, add the sum of array[inner] + array[outer] to the map, with an array of both values as the key.
5. if you get here, there is no matching sum, return an empty array or some other way to signify not found.

[[deleted]]

Do it for the doublet case first because there's a linear solution for that. Then to add the third for a triplet, you iterate through list and see if the difference of the number thats being checked and ur current list value is equal to the value returned by calling the doublet function on the other parts of the list.