C#, with comments on every line, so that everyone can understand it even if they don't speak the language:
The simple, O(n2) solution - using a nested loop.
(intIndex1,intIndex2)TwoSum(int[]array,inttarget){// iterate the array from 0 to length -2for(vari=0;i<array.Length-1;i++){// iterate the array from i+1 to length -1for(varj=i+1;j<array.Length;j++){// if sum foundif(array[i]+array[j]==target){// return both indexesreturn(i,j);}}}// indicate no match found, required by the c# compier.return(-1,-1);}
The sophisticated, O(n) solution - using a single loop and a helper hash map.
intIndex1,intIndex2)TwoSumImproved(int[]array,inttarget){// In .Net, A dictionary is basically a hash map. here the keys and values are both intsvarmap=newDictionary<int,int>();// iterate the full length of the array.for(vari=0;i<array.Length;i++){// calculate the value needed to add to the current value to get the target sumvarvalueNeeded=target-array[i];// check if the map contains the value needed as it's key, If it does, return true and populate the int j// The TryGetValue time complexity is approaching O(1)if(map.TryGetValue(valueNeeded,outintj)){// return both indexesreturn(j,i);}// add to the map, where the key is the array value and the value is the index.map.Add(array[i],i);}return(-1,-1);// indicate no match found}
The input will always be valid that's even worst than premature optimizations.
However, for the purpose of this challenge, I'll take that assumption, because while super important, input validation is boring.
My answer inspired by willsmart's answer.
C#, with comments on every line, so that everyone can understand it even if they don't speak the language:
The simple, O(n2) solution - using a nested loop.
The sophisticated, O(n) solution - using a single loop and a helper hash map.
Try it online