11 Apr 2018
Problem Description
- Find the number of 3-sum in an array of distinct integers that add up to 0.
- The algorithm should take time proportional to n^2.
Personal Thoughts
- Firstly, convert this problem into a two-sum problem and we can solve the two-sum in O(n) time with a HashMap.
- Initialize a counter to zero and this counter is used to keep track of the number of 3-sum.
- Keep an outer loop to iterate through the array. For each item in the array, deduct 0 by that item, for example, if the first number in the array is 8, then 0 - 8 = -8.
- Then we store the above value into a variable and solve a 2-sum problem on the rest of the array items. For example, find out all distinct pairs which add up to -8.
- When we iterate through each of the remaining items, we treat (the value of the above-mentioned variable - value each item) as keys and the index of the corresponding item as values in the HashMap.
- While iterating through the remaining items, check whether they have already been stored in the HashMap as keys. If yes, increment the counter by one, if no, continue looping.
- repeat step 4 to 6 until the outer loop reaches index, n - 2 item.
- return counter value as the number of 3-sum.