Given unsorted list we would like to find one or more pairs of three numbers that will add up to a given target value K. For the sake of simplicity you can assume K=0.
Example: int[] nums = { -1, 1, -1, 5, -3, -5, 6, 2, -4, 7 };
Ans: There are 5 pairs that add up to 0. {-5,-1,6} {-4,-3,-7} {-4,-1,5} {-3,1,2} {-1,-1,2}
Solution:
Step 1: We sort the list in ascending order in nlog(n) time. This is the time complexity of this algorithm
Step 2: We will have three indexes (i, j and k) where i and j traverse the array forward but k backwards.
In each iteration we will check three things:
- If nums(i) + nums(j) + nums(k) < 0, then j++ because in a sorted array if the sum of the three numbers is less than target, it means we need to try greater values which are found going forward since array is sorted in ascending order.
- If nums(i) + nums(j) + nums(k) > 0, then k-- because in a sorted array if the sum of the three numbers is greater than target, it means we need to try smaller values which are found going backwards since array is sorted in ascending order.
- If nums(i) + nums(j) + nums(k) = 0, then it means we found our pair and we need to save that in a list of lists.
Note: We can use HashSet of KeyValuePair to check for duplicate pairs. We want to make sure each pair we put in the answer list is unique.
public static List<List<int>> ThreeSumer(int[] nums) {
if (nums == null || nums.Length == 0) return new List<List<int>>();
Array.Sort(nums);
List<List<int>> res = new List<List<int>>();
HashSet<KeyValuePair<int, int>> set = new HashSet<KeyValuePair<int, int>>();
for (int i = 0; i < nums.Length - 2; i++) {
int j = i + 1, k = nums.Length - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] > 0) k--;
else if (nums[i] + nums[j] + nums[k] < 0) j++;
else {
if (!set.Contains(new KeyValuePair<int, int>(nums[i], nums[j]))) {
List<int> pair = new List<int>();
pair.Add(nums[i]);
pair.Add(nums[j]);
pair.Add(nums[k]);
res.Add(pair);
set.Add(new KeyValuePair<int, int>(nums[i], nums[j]));
}
j++;
k--;
}
}
}
return res;
}