[알고리즘] 1. Two Sum

1. 브루트 포스를 이용한 풀이

public class TwoSum_1
{
    public int[] twoSum_1(int[] nums, int target)
    {
	int len = nums.length;
        int first = 0 , second = 0;
        
        OUT : for(int i = 0; i < len-1; ++i)
        {
            first = i;
           
            for(int j = i+1; j < len; ++j)
            {
            	if(nums[i] + nums[j] == target)
                {    
                    second = j;
                    break OUT;
                }
            }
        }

        int[] temp = new int[2];
        temp[0] = first;
        temp[1] = second;
        
        return temp;
    }
}

브루트 포스로 푸는 경우 2중첩 for loop에 의해 시간복잡도는 O(n^2)이 된다.

2. 해쉬 맵을 이용한 풀이

https://www.code-recipe.com/post/two-sum

public class TwoSum_2
{
	public int[] twoSum_2(int[] array, int target)
	{
		HashMap<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
		
		for(int i=0; i<array.length; ++i)
		{
			int requireNum = (int)(target - array[i]);
			
			if(indexMap.containsKey(requireNum))
			{
				int toReturn[] = {indexMap.get(requireNum),i};
				return toReturn;
			}
			indexMap.put(array[i], i);					
		}
		
		return null;
	}
}

• 해쉬 맵을 사용한 경우 O(n)의 시간복잡도로 알고리즘을 수행한다.

3. 투포인터 알고리즘을 사용한 풀이.

• 배열이 정렬되어있지 않기때문에, 투포인터 알고리즘을 사용할 수 없다.