Two Sum

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Easy

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/TwoSum/

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

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

Solution

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int index = -1, idx1 = -1, idx2 = -1;
        int[] copy = nums;
        nums = Divide(nums);

        for (int k = 0; k < nums.Length; k++)
        {
            index = -1;
            BinarySearch(nums, target - nums[k], 0, ref index);

            if (index == -1)
            {
                continue;
            }

            if (nums[index] * 2 == target)
            {
                return SearchMultipleIndex(copy, nums[index]);
            }
            else
            {
                idx1 = k;
                break;
            }
        }

        idx2 = SearchIndex(copy, nums[index]);
        int idx3 = SearchIndex(copy, nums[idx1]);
        return new int[] { idx3, idx2 };
    }

    public void BinarySearch(int[] nums, int target, int indexnow, ref int index)
    {
        if (nums.Length < 2)
        {
            if (nums[0] == target)
            {
                index = indexnow;
            }
            else
            {
                return;
            }
        }

        int pivot = (int)(nums.Length / 2);

        if (nums[pivot] > target)
        {
            BinarySearch(nums[0..pivot], target, indexnow, ref index);
        }
        else if (nums[pivot] < target)
        {
            BinarySearch(nums[pivot..(nums.Length)], target, indexnow + pivot, ref index);
        }
        else
        {
            index = indexnow + pivot;
        }
    }

    public int SearchIndex(int[] nums, int target)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == target)
            {
                return i;
            }
        }

        return 0; // not searched
    }

    public int[] SearchMultipleIndex(int[] nums, int target)
    {
        int itmp1 = -1;
        bool foundfirstone = false;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == target && foundfirstone == false)
            {
                itmp1 = i;
                foundfirstone = true;
                continue;
            }
            else if (nums[i] == target && foundfirstone == true)
            {
                return new int[] { itmp1, i };
            }
        }

        return new int[] { 0 }; // not searched
    }

    public int[] Divide(int[] nums)
    {
        if (nums.Length < 2)
        {
            return nums;
        }

        int pivot = (int)(nums.Length / 2);
        int[] leftarray = nums[0..pivot];
        int[] rightarray = nums[pivot..(nums.Length)];

        leftarray = Divide(leftarray);
        rightarray = Divide(rightarray);

        return Merge(leftarray, rightarray);
    }

    public int[] Merge(int[] leftarray, int[] rightarray)
    {
        int l = leftarray.Length - 1;
        int r = rightarray.Length - 1;
        int[] temp = new int[leftarray.Length + rightarray.Length];

        while (l >= 0 && r >= 0)
        {
            if (leftarray[l] > rightarray[r])
            {
                temp[l + r + 1] = leftarray[l];
                l--;
            }
            else
            {
                temp[l + r + 1] = rightarray[r];
                r--;
            }
        }

        while (l >= 0)
        {
            temp[l] = leftarray[l];
            l--;
        }

        while (r >= 0)
        {
            temp[r] = rightarray[r];
            r--;
        }

        return temp;
    }
}

Comment

Idea : 크기 순서대로 정렬을 하자. 내가 a를 골랐고, n을 만들어야 한다면 찾아야 하는 숫자는 n-a. 즉 배열을 정렬했을 때 이진 검색 알고리즘을 이용하면 간단히 n-a를 찾을 수 있다.
Divide(nums) / Merge(nums) : Merge Sort를 직접 구현함.
먼저 주어진 nums를 divide에 넣은 뒤, 새로운 배열을 선형적으로 n의 보수를 Binary Search한다.

Merge Sort란?

합쳐진 한 개의 리스트를 2개의 리스트로 분할하고, 이를 반복하여 원소의 갯수가 1인 작은 리스트들로 분할될 때까지 반복한다.
두 개의 리스트를 합칠때에는 다음의 과정을 따른다 : 두 List의 0번째 index부터 순차적으로 비교하여 작은 것을 새로운 리스트로 옮기고, 이를 한 List의 원소가 다 떨어질 때까지 반복한다. 남아있는 List의 원소들을 순서대로 새로운 리스트에 덧붙이고 새로운 리스트를 Merge sort된 SubArray로 본다.
위 과정을 재귀적으로 반복하여 오름차순 정렬된 새로운 리스트를 얻을 수 있다.
Divide : 함수의 앞쪽 부분에서 Array 길이의 1/2 지점을 기준으로 두 개의 Array로 나누고, 나누어진 좌우의 Array에 대해 재귀적으로 Divide를 적용한다. Divide할 Array의 크기가 1이라면 Merge를 수행한다.
Merge : 좌측과 우측 Array를 상술한 방법을 이용해 새로운 Array로 합친다. Divide에서 나눈 순서대로 Merge하므로, Merge는 단순히 순서를 적용해 합쳐주기만 하면 된다.
전체 과정을 통틀었을 때 Time complixity는 O(nlogn)이며, 최악의 상황에서도 O(nlogn)을 보장하므로, 정렬 알고리즘 중 의미가 있다고 판단하여 직접 구현해 보았다.

Binary Search란?

이진 서치, 혹은 바이너리 서치는 오름차순 혹은 내림차순으로 정렬된 배열에서 O(logn)의 Time complixity를 이용하여 간단히 주어진 값을 찾는 방법이다. 정렬된 배열에서는 O(n)의 기존 Linear Search보다 빠르므로 편하게 사용할 수 있지만, 정렬되지 않은 배열에서 Binary Search를 사용하려면 추가적으로 정렬과정에서 O(nlogn)의 과정이 필요하므로, 특수한 case에서 사용해볼법하다.
아이디어는 간단하다. 술게임 등에서 업다운 게임을 생각하면 쉽다. 원소가 100개인 정렬된 배열 중 특정 숫자(40)를 찾는다고 생각해보자.
50th idx의 값을 읽는다 -> 67이 나옴. (1~50th 사이에 찾고자 하는 값이 있으므로 범위를 좁힌다.)
25ty idx의 값을 읽는다 -> 36이 나옴. (26th ~ 49th 사이로 범위를 좁힌다.)
동일한 과정을 반복하면, 최대 logn번의 연산으로 특정값을 찾을 수 있다.
개선 방법 : 해쉬맵(Hashmap)을 이용하면, 특정값과 그 index를 순서쌍의 형태로 저장할 수 있어서 Search에서 시간 개선이 가능하다.

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        Dictionary<int, int> array = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++)
        {
            int key = target - nums[i];

            if (array.ContainsKey(key))
            {
                return new int[] { array[key], i };
            }
            else if (!array.ContainsKey(nums[i]))
            {
                array.Add(nums[i], i);
            }
        }

        return new int[] { 0 }; // for non-error
    }
}

Hashmap을 이용하기 위해 System.Collections.Generic 라이브러리를 참조하여 제네릭 딕셔너리 자료형을 선언하여 구현가능하다.
nums를 0th idx부터 훑으며 target-nums[i]를 Dictionary에서 찾는다. 없다면 저장하고 있다면 그 값을 반환한다.
역시나 time complexity는 O(nlogn)임에 변함이 없으나, O(logn)에 해당하는 Search 과정에서 Dictionary를 이용하면 훨씬 효율적으로 서치할 수 있는 모양이다. 더군다나 코드가 깔끔하다. (위쪽 코드도 정렬을 직접 구현하지 않았다면 간단했겠지만)

댓글을 불러오는 중입니다.