Nav: << previous: - | next: 2.两数相加 >>
Description
tab: English
<p>Given an array of integers <code>nums</code> and an integer <code>target</code>, return <em>indices of the two numbers such that they add up to <code>target</code></em>.</p>
<p>You may assume that each input would have <strong><em>exactly</em> one solution</strong>, and you may not use the <em>same</em> element twice.</p>
<p>You can return the answer in any order.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<pre>
<strong>Input:</strong> nums = [2,7,11,15], target = 9
<strong>Output:</strong> [0,1]
<strong>Explanation:</strong> Because nums[0] + nums[1] == 9, we return [0, 1].
</pre>
<p><strong class="example">Example 2:</strong></p>
<pre>
<strong>Input:</strong> nums = [3,2,4], target = 6
<strong>Output:</strong> [1,2]
</pre>
<p><strong class="example">Example 3:</strong></p>
<pre>
<strong>Input:</strong> nums = [3,3], target = 6
<strong>Output:</strong> [0,1]
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>2 <= nums.length <= 10<sup>4</sup></code></li>
<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
<li><code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code></li>
<li><strong>Only one valid answer exists.</strong></li>
</ul>
<p> </p>
<strong>Follow-up: </strong>Can you come up with an algorithm that is less than <code>O(n<sup>2</sup>)</code><font face="monospace"> </font>time complexity?
> [!tip]- Hint 1
>
> A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions just for completeness. It is from these brute force solutions that you can come up with optimizations.
> [!tip]- Hint 2
>
> So, if we fix one of the numbers, say <code>x</code>, we have to scan the entire array to find the next number <code>y</code> which is <code>value - x</code> where value is the input parameter. Can we change our array somehow so that this search becomes faster?
> [!tip]- Hint 3
>
> The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
---
[submissions](https://leetcode.com/problems/two-sum/submissions/) | [solutions](https://leetcode.com/problems/two-sum/solutions/)
tab: 中文
<p>给定一个整数数组 <code>nums</code> 和一个整数目标值 <code>target</code>，请你在该数组中找出 <strong>和为目标值 </strong><em><code>target</code></em> 的那 <strong>两个</strong> 整数，并返回它们的数组下标。</p>
<p>你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。</p>
<p>你可以按任意顺序返回答案。</p>
<p> </p>
<p><strong class="example">示例 1：</strong></p>
<pre>
<strong>输入：</strong>nums = [2,7,11,15], target = 9
<strong>输出：</strong>[0,1]
<strong>解释：</strong>因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
</pre>
<p><strong class="example">示例 2：</strong></p>
<pre>
<strong>输入：</strong>nums = [3,2,4], target = 6
<strong>输出：</strong>[1,2]
</pre>
<p><strong class="example">示例 3：</strong></p>
<pre>
<strong>输入：</strong>nums = [3,3], target = 6
<strong>输出：</strong>[0,1]
</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>2 <= nums.length <= 10<sup>4</sup></code></li>
<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
<li><code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code></li>
<li><strong>只会存在一个有效答案</strong></li>
</ul>
<p> </p>
<p><strong>进阶：</strong>你可以想出一个时间复杂度小于 <code>O(n<sup>2</sup>)</code> 的算法吗？</p>
> [!tip]- 提示 1
>
> A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions just for completeness. It is from these brute force solutions that you can come up with optimizations.
> [!tip]- 提示 2
>
> So, if we fix one of the numbers, say <code>x</code>, we have to scan the entire array to find the next number <code>y</code> which is <code>value - x</code> where value is the input parameter. Can we change our array somehow so that this search becomes faster?
> [!tip]- 提示 3
>
> The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
---
[提交记录](https://leetcode.cn/problems/two-sum/submissions/) | [题解](https://leetcode.cn/problems/two-sum/solution/)
Solutions & Notes
properties:
note.updated:
displayName: Last Updated
note.relative_links:
displayName: Related Links
note.desc:
displayName: Description
note.grade:
displayName: Rating
note.program_language:
displayName: Language
note.time_complexity:
displayName: TC
note.space_complexity:
displayName: SC
views:
- type: table
name: Solutions & Notes
filters:
and:
- file.hasLink(this.file)
- file.tags.containsAny("leetcode/solution", "leetcode/note")
order:
- file.name
- desc
- program_language
- time_complexity
- space_complexity
- grade
- relative_links
- updated
sort:
- property: grade
direction: ASC
- property: time_complexity
direction: ASC
- property: program_language
direction: ASC
columnSize:
file.name: 104
note.space_complexity: 65
note.grade: 126
Similar Problems
properties:
note.lcTopics:
displayName: Topics
note.lcAcRate:
displayName: AC Rate
note.favorites:
displayName: Favorites
note.grade:
displayName: Rating
note.translatedTitle:
displayName: Title (CN)
note.lcDifficulty:
displayName: Difficulty
views:
- type: table
name: Similar Problems
filters:
and:
- file.hasLink(this.file)
- similarQuestions.contains(this.file)
order:
- file.name
- translatedTitle
- lcTopics
- lcDifficulty
- lcAcRate
- grade
- favorites
sort:
- property: file.name
direction: ASC
- property: lcTopics
direction: DESC
columnSize:
note.translatedTitle: 240
note.lcTopics: 347
note.lcAcRate: 75
note.grade: 122