O(n) complexity C# code


  • 0
    X
    public int[] TwoSum(int[] nums, int target) {
            
            Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();
            int[] result = new int[2];
            
            for(int i=0; i<nums.Length; i++)
            {
                List<int> value = null;
                
                if (map.TryGetValue(nums[i], out value))
                {
                    value.Add(i);
                }
                else
                {
                    value = new List<int>();
                    value.Add(i);
                }
                
                map[nums[i]] = value;
            }
            
            for(int j=0; j<nums.Length; j++)
            {
                List<int> outValue = null;
                
                if(map.TryGetValue(target-nums[j], out outValue))
                {
                    for(int k=0; k<outValue.Count; k++)
                    {
                        if (outValue[k] != j)
                        {
                            result[0] = j;
                            result[1] = outValue[k];
                            break;
                        }
                    }
                }
            }
            
            return result;
        }
    

  • 0
    B

    You can use the Dictionary<int, int> instead of Dictionary<int, List<int>>

    public class Solution {
       public int[] TwoSum(int[] nums, int target) {
            int[] results = new int[2];
            Dictionary<int, int> dict = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i += 1)
            {
                if (dict.ContainsKey(target - nums[i]))
                    return new int[] { dict[target - nums[i]], i };
                if(dict.ContainsKey(nums[i]))
                    continue;
                dict.Add(nums[i], i);
            }
            return results;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.