<h3>📺 视频题解</h3>
<h3>文字题解</h3>
<h4>方法一：暴力枚举</h4>
<p><strong>思路及算法</strong></p>
<p>最容易想到的方法是枚举数组中的每一个数 <code>x</code>，寻找数组中是否存在 <code>target - x</code>。</p>
<p>当我们使用遍历整个数组的方式寻找 <code>target - x</code> 时，需要注意到每一个位于 <code>x</code> 之前的元素都已经和 <code>x</code> 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 <code>x</code> 后面的元素中寻找 <code>target - x</code>。</p>
<p><strong>代码</strong></p>
<pre><code class="language-Java">class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i &lt; n; ++i) {
            for (int j = i + 1; j &lt; n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}
</code></pre>
<pre><code class="language-C++">class Solution {
public:
    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {
        int n = nums.size();
        for (int i = 0; i &lt; n; ++i) {
            for (int j = i + 1; j &lt; n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};
</code></pre>
<pre><code class="language-C">int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i &lt; numsSize; ++i) {
        for (int j = i + 1; j &lt; numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i, ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}
</code></pre>
<pre><code class="language-Python">class Solution:
    def twoSum(self, nums: List[int], target: int) -&gt; List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []
</code></pre>
<pre><code class="language-Golang">func twoSum(nums []int, target int) []int {
    for i, x := range nums {
        for j := i + 1; j &lt; len(nums); j++ {
            if x+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}
</code></pre>
<p><strong>复杂度分析</strong></p>
<ul>
<li>
<p>时间复杂度：$O(N^2)$，其中 $N$ 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。</p>
</li>
<li>
<p>空间复杂度：$O(1)$。</p>
</li>
</ul>
<h4>方法二：哈希表</h4>
<p><strong>思路及算法</strong></p>
<p>注意到方法一的时间复杂度较高的原因是寻找 <code>target - x</code> 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。</p>
<p>使用哈希表，可以将寻找 <code>target - x</code> 的时间复杂度降低到从 $O(N)$ 降低到 $O(1)$。</p>
<p>这样我们创建一个哈希表，对于每一个 <code>x</code>，我们首先查询哈希表中是否存在 <code>target - x</code>，然后将 <code>x</code> 插入到哈希表中，即可保证不会让 <code>x</code> 和自己匹配。</p>
<p><strong>代码</strong></p>
<pre><code class="language-Java">class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map&lt;Integer, Integer&gt; hashtable = new HashMap&lt;Integer, Integer&gt;();
        for (int i = 0; i &lt; nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}
</code></pre>
<pre><code class="language-C++">class Solution {
public:
    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {
        unordered_map&lt;int, int&gt; hashtable;
        for (int i = 0; i &lt; nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it-&gt;second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};
</code></pre>
<pre><code class="language-C">struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &amp;ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp-&gt;key = ikey, tmp-&gt;val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it-&gt;val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i &lt; numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it-&gt;val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}
</code></pre>
<pre><code class="language-Python">class Solution:
    def twoSum(self, nums: List[int], target: int) -&gt; List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []
</code></pre>
<pre><code class="language-Golang">func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, x := range nums {
        if p, ok := hashTable[target-x]; ok {
            return []int{p, i}
        }
        hashTable[x] = i
    }
    return nil
}
</code></pre>
<p><strong>复杂度分析</strong></p>
<ul>
<li>
<p>时间复杂度：$O(N)$，其中 $N$ 是数组中的元素数量。对于每一个元素 <code>x</code>，我们可以 $O(1)$ 地寻找 <code>target - x</code>。</p>
</li>
<li>
<p>空间复杂度：$O(N)$，其中 $N$ 是数组中的元素数量。主要为哈希表的开销。</p>
</li>
</ul>