leetcode/two_sum

two_sum

dz / leetcode / two_sum

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/two-sum

problem
content two-sum: given an array of integers =nums= and an integer =target=, return indices of the two numbers such that they add up to =target=. You may assume that each input would have exactly one solution, and may not use the same element twice.
children cpp_impl, intuition

intuition
content This can be solved using brute force using two loops. For each number, add it with every other number, and return the pair if it adds up to the target. This yields a performance time of O(n^2).
children better_performance (follow-up, how to do better performance)
parents problem

better_performance
content This can be solved in less than O(n^2) time by realizing that pairs can be in any order. Comparing indices A and B is equivalent to B and A. My gut tells me that this cuts it in half, so O(n^2)/2, but I have yet to prove it.
children caching_vs_smaller_inner_loop (I thought about using a smaller inner loop), better_impl (how to implement)
parents intuition

better_impl
content How to keep track of pairs already done? There's always brute-force of keeping track. But, you can also order the pairs. There is a total ordering here, and you can choose to only consider pairs where A < B. If the outer loop is A, the inner loop is B, the inner loop could iterate up to A.
parents better_performance

cpp_impl
content The CPP solutions don't implement the naive n^2 solution and instead use hash maps to cache results to remove the inner loop used for searching, reducing performance from O(n) to O(1).
children unordered_map_cpp, caching_vs_smaller_inner_loop (the solutions here use caching via an unordered map), subtract_from_target
parents problem

subtract_from_target
content There are two implementations, but the gist is to keep track of the target minus the number in the map, the idea being that that key is the only solution for to make that number work. The value stored is the indice. If the matching pair is found, it will be a hit on the map, and the two indices are returned.
children relies_on_exactly_one_answer
parents cpp_impl

unordered_map_cpp
content Uses an unordered map in C++
parents cpp_impl
remarks find() and end() methods are used. If find() == end(), it means it is not in there.
hyperlink https://en.cppreference.com/w/cpp/container/unordered_map

relies_on_exactly_one_answer
content The problem states there is exactly one answer, which rules out the possibility of accidently returning the same indices.
parents subtract_from_target

caching_vs_smaller_inner_loop
content My initial idea was to use a smaller inner loop to remove redundancies in searching for an answer. I referred to caching as a solution that only works if you have the memory for it. I was thinking about a 2d matrix, which is very memory-intensive. The C++ uses a map which is way more clever.
parents cpp_impl, better_performance