[Toggle Comments]
package main // file: impl-002.go // Two pass using a map. // // Create a reverse lookup table that maps numbers to indexes. // // time: O(n); space: O(n). func twoPassHashTable(nums []int, target int) []int { // The time complexity of a map lookup is “amortized constant time”, // so it will save time on average. // // Let’s create a reverse lookup table that maps values to indexes. // // Observe that (as per the problem statement) we have exactly one // solution. That can **only** happen if all the numbers in the `nums` // slice are unique. // // For instance, nums=[1,1,2]; target=3 will give two solutions: // (0,2) and (1,2) because we are free to choose either of the `1`s // in index 0, or index 1. // // If we didn’t have this constraint, using a map would not have worked // out for us. indexes := make(map[int]int, len(nums)) for i, n := range nums { // The index of `n` is `i. indexes[n] = i } for i, n := range nums { complement := target - n j, found := indexes[complement] // Cannot match a number with itself, try the next one. if j == i { continue } // Not found, try the next one. if !found { continue } // Found a match. return []int{i, j} } // No match found. // This should never happen as per our problem definition. return []int{-1, -1} } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */