DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Cover image for Two Sum
FakeStandard
FakeStandard

Posted on • Updated on

Two Sum

#1.Two Sum

Problem statement

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].
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]
Enter fullscreen mode Exit fullscreen mode

Explanation

ๅพž็ตฆๅฎš็š„ array ไธญๆ‰พๅˆฐๅ…ฉๅ€‹ๆ•ธ็›ธๅŠ ็ญ‰ๆ–ผ target๏ผŒไธฆไธ”่ฟ”ๅ›žๅ…ฉๆ•ธ็ดขๅผ•

  • ๅชๆœƒๆœ‰ไธ€ๅ€‹ๆœ‰ๆ•ˆ็ญ”ๆกˆ
  • ๅŒไธ€ๅ€‹ๅ…ƒ็ด ไธๆœƒไฝฟ็”จๅ…ฉๆฌก
  • ๅฏไปฅ่ฟ”ๅ›žไปปไฝ•้ †ๅบ็š„็ดขๅผ•

Solution

ๆฏ”่ผƒ็›ด่ฆบๅœฐๆ–นๅผๆ˜ฏไฝฟ็”จ้›™่ฟดๅœˆ่ฟญไปฃ้™ฃๅˆ—ไพ†่งฃ๏ผŒ้€™็จฎๆšดๅŠ›่งฃๆณ•้‡ๅˆฐ่ณ‡ๆ–™้‡่ผƒๅคงๆ™‚๏ผŒ้œ€่ฆๆ›ดๅคšๆ™‚้–“ไพ†ๅฎŒๆˆใ€‚

ๅฆ‚ๆžœไปฅๆ™‚้–“่ค‡้›œๅบฆไฝœ็‚บ่€ƒ้‡๏ผŒ้œ€่จญๆณ•ๆธ›ๅฐ‘่ฟดๅœˆ็š„ไฝฟ็”จๆฌกๆ•ธ๏ผŒ่ฎ“ๅŸท่กŒๆ™‚้–“ๅคงๅน…ไธ‹้™๏ผŒ้‚ฃ้บผๅฏไฝฟ็”จไธ€ๅ€‹้กๅค–็ฉบ้–“ไพ†ๅ„ฒๅญ˜ๅ…ƒ็ด ๏ผŒไปฅ้”ๅˆฐ็ฉบ้–“ๆ›ๆ™‚้–“็š„ๆƒณๆณ•๏ผŒ้›–็„ถๆญคๆ–นๆณ•่ฎ“ๆ™‚้–“่ค‡้›œๅบฆ้™ไฝŽ๏ผŒๅŒๆ™‚ไนŸๆ้ซ˜ไบ†็ฉบ้–“่ค‡้›œๅบฆใ€‚

Array
้€้Ž้›™่ฟดๅœˆ้€ไธ€่ตฐ่จช้™ฃๅˆ—๏ผŒๅ› ็‚บๅ…ƒ็ด ไธๅฏ้‡่ค‡๏ผŒๆ•…ๅ– 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;
}
Enter fullscreen mode Exit fullscreen mode

HashTable
ไฝฟ็”จไธ€ๅ€‹้กๅค–็ฉบ้–“ 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;
}
Enter fullscreen mode Exit fullscreen mode

Dictionary
ไธ€ๆจฃไฝฟ็”จไธ€ๅ€‹้กๅค–็ฉบ้–“ 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;
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article ๐ŸŒท ๐ŸŒป ๐ŸŒผ

If you like it, please don't hesitate to click heart button โค๏ธ
or click like on my Leetcode solution
or follow my GitHub โญ
or buy me a coffee โฌ‡๏ธ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)

Make Your Github Profile Stand Out

Github is great, but have you considered how to make yours more attractive for potential employers or other visitors? Even non-tech ones like recruiters!

Take a couple of hours and show your best side as a person - and a programmer.