Description
The idea is to find any 2 values within a list of numbers that satisfy a condition. There are many approaches to this problem but one fast approach is to use a sorted dictionary which reduces iterations
static void FindPairs(int[] numbers, int sum) { SortedDictionary<int, int> Map = new SortedDictionary<int, int>(); for (int i = 0; i < numbers.Length; i++) { int number = numbers[i]; if (Map.ContainsValue(sum - number)) { int mKey = Map.Where(x => x.Value == (sum - number)).First().Key; Console.WriteLine("a[{0}]:{1} + a[{2}]:{3}", i, number, mKey, (sum - number)); } Map.Add(i, number); } }
Using A Condition
Using a condition to test the relation between 2 values is easily achieved by replacing a fixed sum with a Func but in this case we will need to iterate the existing dictionary for matching values. Since the Dictionary is built on each first set of iterations the complexity does not reach O2
static void FindPairsPredicate(int[] numbers, Func<int, int, bool> condition) { SortedDictionary<int, int> Map = new SortedDictionary<int, int>(); for (int i = 0; i < numbers.Length; i++) { int number = numbers[i]; IEnumerable<KeyValuePair<int, int>> find = Map.Where(x => condition(number, x.Value)); if (find.Count() > 0) { KeyValuePair<int, int> first = find.First(); int value = first.Value; int key = first.Key; Console.WriteLine("a[{0}]:{1} + a[{2}]:{3}", i, number, key, value); } Map.Add(i, number); } }
Usage
FindPairs(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 10); FindPairsPredicate(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, (first, second) => { return (first + second) == 10 && first < 7; });