Instantly share code, notes, and snippets.

# jianminchen/FindTwoItemsWithGivenSum.cs Created Mar 27, 2018

Unsorted array asked to find two items with sum equal to the given value. Use extra dictionary to store the key and value.
 using System; using System.Collections.Generic; class Solution { public static int[] GetIndicesOfItemWeights(int[] arr, int limit) { // [4, 6, 10, 15, 16], 21 if(arr == null) // false return new int[0]; var length = arr.Length; // 5 var dict = new Dictionary(); for(int i = 0; i < length; i++) { var current = arr[i]; // 4, 6, 10, 15 var search = limit - current; // 17, 15, 11, 6 if(dict.ContainsKey(search)) // true { return new int[]{i, dict[search]}; // [3, 1] } else { if(dict.ContainsKey(current)) // 4 { dict[current] = i; } else dict.Add(current, i); // 4:0, 6:1, 10:2 } } return new int[0]; } static void Main(string[] args) { } } /* keywords: array - sorted? Ask: find two items with sum equals to given limit index [i, j] where i > j, arr[i] + arr[j] = limit Hashmap -> [4, 6, 10, 15, 16] -> 4, check hashmap 21 - 4 = 17, if it is in hashmap, put 4: 0 into hashmap 6, look for 21 - 6 = 15 -> hashmap put 6: 1 into hashmap 10, 21 - 10 = 11, not found put 10:2 into hashmap 15, 21 - 15 = 6, find in hashmap, 1, return [3, 1] Space complexity: O(n), size of the array time complexity: O(n), n is size of the array */
Owner Author

### jianminchen commented Mar 27, 2018

 I finished the analysis and coding in ten minutes, and then the peer asked me to work on an example, and then I did go over the example until the pair of indexes are found. Please do not skip the testing the code using an example.