2합

#1.투썸

문제 설명

정수 배열 nums 과 정수 target 가 주어지면 두 숫자의 인덱스를 모두 합하면 target 이 됩니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

예 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

예 2

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

예 3

Input: nums = [3,3], target = 6
Output: [0,1]

설명

從給定的 array 中找到兩個數相加等於 target ,並且返回兩數索引

只會有一個有效答案

同一個元素不會使用兩次

可以返回任何順序的索引

해결책

比較直覺地方式是使用雙迴圈迭代陣列來解,這種暴力解法遇到資料量較大時,需要更多時間來完成.

如果以時間複雜度作為考量,需設法減少迴圈的使用次數,讓執行時間大幅下降,那麼可使用一個額外空間來儲存元素,以達到空間換時間的想法,雖然此方法讓時間複雜度降低,同時也提高了空間複雜度.

정렬
透過雙迴圈逐一走訪陣列,因為元素不可重複,故取 i+1 略過自己以及計算過的值

public int[] TwoSum(int[] nums, int target)
{
    int i, j;

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

    return null;
}

해시 테이블
使用一個額外空間 HashTable ,以達到用空間換取時間

public int[] TwoSum(int[] nums, int target)
{
    Hashtable hash = new Hashtable();

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

        if (hash.ContainsKey(diff))
            return new int[] { i, (int)hash[diff] };

        if (!hash.ContainsKey(num))
            hash.Add(num, i);
    }

    return null;
}

사전
一樣使用一個額外空間 Dictionary 達到空間換時間的目的

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

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

        if (dic.ContainsKey(diff))
            return new int[] { i, (int)dic[diff] };

        if (!dic.ContainsKey(num))
            dic.Add(num, i);
    }

    return null;
}

참조

LeetCode Solution

GitHub Repository


글 읽어주셔서 감사합니다 🌷 🌻 🌼

마음에 드셨다면 주저말고 하트 꾸욱 눌러주세요❤️
또는 내 Leetcode 솔루션에서 좋아요를 클릭하세요.
또는 내 GitHub ⭐ 팔로우
또는 커피를 사주세요 ⬇️ 감사합니다.