[LeetCode] Two Sum

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

알고리즘 유형

- 부르트포스 

- 해시 

 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Two_Sum
{
    class Program
    {
        static void Main()
        {
            int[] nums = { 2, 7, 11, 15 };
            int target = 9;
            var result = new Solution().TwoSum(nums, target);
            Console.Write("[");
            for (int i = 0; i < result.Length; i++)
            {
                Console.Write("{0}", result[i]);
                if (i < result.Length - 1)
                {
                    Console.Write(",");
                }
            }
            Console.Write("]");

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

 

3개의 테스트케이스는 통과 했지만 반례가 있음

 

public int[] TwoSum(int[] nums, int target) {    
    Dictionary<int, int> valToIndex = new Dictionary<int, int>(nums.Length);
    for (int i = 0; i < nums.Length; i++) {
        if (valToIndex.ContainsKey(target - nums[i])) {
            return new int[] { valToIndex[target - nums[i]], i };
        }
        valToIndex[nums[i]] = i;
    }
    return new int[] { -1, -1 };
}

 

 

 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Two_Sum
{
    class Program
    {
        static void Main()
        {
            int[] nums = { 2, 7, 11, 15 };
            int target = 9;
            var result = new Solution().TwoSum(nums, target);
            Console.Write("[");
            for (int i = 0; i < result.Length; i++)
            {
                Console.Write("{0}", result[i]);
                if (i < result.Length - 1)
                {
                    Console.Write(",");
                }
            }
            Console.Write("]");

        }
    }
    
    public class Solution {
        public int[] TwoSum(int[] nums, int target) {    
            Dictionary<int, int> dic = new Dictionary<int, int>(nums.Length);
            for (int i = 0; i < nums.Length; i++) {
                //2, 7, 11, 15
                //target: 9
                //7, 2, -2, -6
                if (dic.ContainsKey(target - nums[i])) {
                                                        //0, 1
                    return new int[] { dic[target - nums[i]], i };
                }
                // {2:0}, 
                dic[nums[i]] = i;
            }
            return new int[] { -1, -1 };
        }

    }
    
}

 

반환 배열의 첫 요소는 확정적으로 들어 갈수 있지만 

두번째 요소는 상황에 따라 안들어 갈수도 있음

 

반환 되는 시점에서 현재 인덱스가 2번째 값임을 알수 있다 

때문에 아래와 같이 두번째 요소의 값은 반환 시점의 i 값이다 

 

return new int[] { dic[diff], i };

 

풀이 

https://mwindle.github.io/two-sum