Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0b06341

Browse files
committed
Added solutions ofzh.
1 parent242e90f commit0b06341

File tree

76 files changed

+20196
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

76 files changed

+20196
-0
lines changed

‎zh/1-1000/1-two-sum.md

Lines changed: 326 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,326 @@
1+
#1. Two Sum - LeetCode Solution
2+
LeetCode problem link:[1. Two Sum](https://leetcode.com/problems/two-sum),
3+
[1. 两数之和](https://leetcode.cn/problems/two-sum)
4+
5+
[中文题解](#中文题解)
6+
7+
##LeetCode problem description
8+
Given an array of integers`nums` and an integer`target`, return_indices of the two numbers such that they add up to`target`_.
9+
10+
You may assume that each input would have**_exactly_ one solution**, and you may not use the same element twice.
11+
12+
You can return the answer in any order.
13+
14+
Difficulty:**Easy**
15+
16+
###[Example 1]
17+
**Input**:`nums = [2,7,11,15], target = 9`
18+
19+
**Output**:`[0,1]`
20+
21+
**Explanation**：`Because nums[0] + nums[1] == 9, we return [0, 1].`
22+
23+
###[Example 2]
24+
**Input**:`nums = [3,2,4], target = 6`
25+
26+
**Output**:`[1,2]`
27+
28+
###[Constraints]
29+
-`2 <= nums.length <= 10**4`
30+
-`-10**9 <= nums[i] <= 10**9`
31+
-`-10**9 <= target <= 10**9`
32+
-**Only one valid answer exists.**
33+
34+
##Solution 1: Two pointers (should master)
35+
[中文题解](#中文题解)
36+
37+
1. The time complexity of the brute force solution is`O(n**2)`. To improve efficiency, you can sort the array, and then use**two pointers**, one pointing to the head of the array and the other pointing to the tail of the array, and decide`left += 1` or`right -= 1` according to the comparison of`sum` and`target`.
38+
2. After finding the two values which`sum` is`target`, you can use the`index()` method to find the`index` corresponding to the value.
39+
40+
###Complexity
41+
* Time:`O(N * log N)`.
42+
* Space:`O(N)`.
43+
44+
##Solution 2: Use Map (also should master)
45+
1. In`Map`,`key` is`num`, and`value` is array`index`.
46+
2. Traverse the array, if`target - num` is in`Map`, return it. Otherwise, add`num` to`Map`.
47+
48+
###Steps
49+
1. In`Map`,`key` is`num`, and`value` is array`index`.
50+
```javascript
51+
let numToIndex=newMap()
52+
53+
for (let i=0; i<nums.length; i++) {
54+
numToIndex.set(nums[i], i)
55+
}
56+
```
57+
58+
2. Traverse the array, if`target - num` is in`Map`, return it. Otherwise, add`num` to`Map`.
59+
```javascript
60+
let numToIndex=newMap()
61+
62+
for (let i=0; i<nums.length; i++) {
63+
if (numToIndex.has(target- nums[i])) {// 1
64+
return [numToIndex.get(target- nums[i]), i]// 2
65+
}
66+
67+
numToIndex.set(nums[i], i)
68+
}
69+
```
70+
71+
###Complexity
72+
* Time:`O(n)`.
73+
* Space:`O(n)`.
74+
75+
##Java
76+
###Solution 1: Two pointers
77+
```java
78+
// Welcome to create a PR to complete the code, thanks!
79+
```
80+
81+
###Solution 2: Using Map
82+
```java
83+
classSolution {
84+
publicint[]twoSum(int[]nums,inttarget) {
85+
var numToIndex=newHashMap<Integer,Integer>();
86+
87+
for (var i=0; i< nums.length; i++) {
88+
if (numToIndex.containsKey(target- nums[i])) {
89+
returnnewint[]{numToIndex.get(target- nums[i]), i};
90+
}
91+
92+
numToIndex.put(nums[i], i);
93+
}
94+
95+
returnnull;
96+
}
97+
}
98+
```
99+
100+
##Python
101+
###Solution 1: Two pointers
102+
```python
103+
classSolution:
104+
deftwoSum(self,nums: List[int],target:int) -> List[int]:
105+
original_nums= nums.copy()
106+
nums.sort()
107+
108+
left=0
109+
right=len(nums)-1
110+
111+
while left< right:
112+
sum_= nums[left]+ nums[right]
113+
114+
if sum_== target:
115+
break
116+
117+
if sum_< target:
118+
left+=1
119+
continue
120+
121+
right-=1
122+
123+
return [original_nums.index(nums[left]),len(nums)-1- original_nums[::-1].index(nums[right])]
124+
```
125+
126+
###Solution 2: Using Map
127+
```python
128+
classSolution:
129+
deftwoSum(self,nums: List[int],target:int) -> List[int]:
130+
num_to_index= {}
131+
132+
for i, numinenumerate(nums):
133+
if target- numin num_to_index:
134+
return [num_to_index[target- num], i]
135+
136+
num_to_index[num]= i
137+
```
138+
139+
##C++
140+
###Solution 1: Two pointers
141+
```cpp
142+
// Welcome to create a PR to complete the code, thanks!
143+
```
144+
145+
###Solution 2: Using Map
146+
```cpp
147+
classSolution {
148+
public:
149+
vector<int> twoSum(vector<int>& nums, int target) {
150+
unordered_map<int, int> num_to_index;
151+
152+
for (auto i = 0; i < nums.size(); i++) {
153+
if (num_to_index.contains(target - nums[i])) {
154+
return {num_to_index[target - nums[i]], i};
155+
}
156+
157+
num_to_index[nums[i]] = i;
158+
}
159+
160+
return {};
161+
}
162+
};
163+
```
164+
165+
##JavaScript
166+
###Solution 1: Two pointers
167+
```javascript
168+
// Welcome to create a PR to complete the code, thanks!
169+
```
170+
171+
###Solution 2: Using Map
172+
```javascript
173+
vartwoSum=function (nums,target) {
174+
let numToIndex=newMap()
175+
176+
for (let i=0; i<nums.length; i++) {
177+
if (numToIndex.has(target- nums[i])) {
178+
return [numToIndex.get(target- nums[i]), i]
179+
}
180+
181+
numToIndex.set(nums[i], i)
182+
}
183+
};
184+
```
185+
186+
##C#
187+
###Solution 1: Two pointers
188+
```c#
189+
// Welcome to create a PR to complete the code, thanks!
190+
```
191+
192+
###Solution 2: Using Map
193+
```c#
194+
publicclassSolution {
195+
publicint[]TwoSum(int[]nums,inttarget) {
196+
varnumToIndex=newDictionary<int,int>();
197+
198+
for (inti=0;i<nums.Length;i++) {
199+
if (numToIndex.ContainsKey(target-nums[i])) {
200+
return [numToIndex[target-nums[i]],i];
201+
}
202+
203+
numToIndex[nums[i]]=i;
204+
}
205+
206+
returnnull;
207+
}
208+
}
209+
```
210+
211+
##Go
212+
###Solution 1: Two pointers
213+
```go
214+
// Welcome to create a PR to complete the code, thanks!
215+
```
216+
217+
###Solution 2: Using Map
218+
```go
219+
functwoSum(nums []int,targetint) []int {
220+
numToIndex:=map[int]int{}
221+
222+
fori,num:=range nums {
223+
ifindex,ok:= numToIndex[target - num]; ok {
224+
return []int{index, i}
225+
}
226+
227+
numToIndex[num] = i
228+
}
229+
230+
returnnil
231+
}
232+
```
233+
234+
##Ruby
235+
###Solution 1: Two pointers
236+
```ruby
237+
# Welcome to create a PR to complete the code, thanks!
238+
```
239+
240+
###Solution 2: Using Map
241+
```ruby
242+
deftwo_sum(nums,target)
243+
num_to_index= {}
244+
245+
nums.each_with_indexdo |num,i|
246+
if num_to_index.key?(target- num)
247+
return [num_to_index[target- num], i]
248+
end
249+
250+
num_to_index[num]= i
251+
end
252+
end
253+
```
254+
255+
##C
256+
```c
257+
// Welcome to create a PR to complete the code of this language, thanks!
258+
```
259+
260+
##Kotlin
261+
```kotlin
262+
// Welcome to create a PR to complete the code of this language, thanks!
263+
```
264+
265+
##Swift
266+
```swift
267+
// Welcome to create a PR to complete the code of this language, thanks!
268+
```
269+
270+
##Rust
271+
```rust
272+
// Welcome to create a PR to complete the code of this language, thanks!
273+
```
274+
275+
##Other languages
276+
```
277+
// Welcome to create a PR to complete the code of this language, thanks!
278+
```
279+
280+
##问题描述
281+
给定一个整数数组`nums` 和一个整数目标值`target`，请你在该数组中找出**和为目标值**`target` 的那**两个** 整数，并返回它们的数组下标。
282+
283+
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
284+
285+
你可以按任意顺序返回答案。
286+
287+
难度:**容易**
288+
289+
###[示例 1]
290+
**输入**:`nums = [2,7,11,15], target = 9`
291+
292+
**输出**:`[0,1]`
293+
294+
**解释**:`Because nums[0] + nums[1] == 9, we return [0, 1].`
295+
296+
#中文题解
297+
##思路1：双指针
298+
1. 暴力解法的时间复杂度为`O(n**2)`，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据**和**情况决定`left += 1`还是`right -= 1`。
299+
2. 找出了两个值后，需要用`index()`方法去找值对应的`index`。
300+
301+
##思路2：使用Map提升查找一个值的效率
302+
1.`Map`中，`key`是`num`，`value`是数组`index`。
303+
2. 遍历数组，如果`target - num`在`Map`中，返回。反之，将`num`加入`Map`中。
304+
305+
###步骤
306+
1.`Map`中，`key`是`num`，`value`是数组`index`。
307+
```javascript
308+
let numToIndex=newMap()
309+
310+
for (let i=0; i<nums.length; i++) {
311+
numToIndex.set(nums[i], i)
312+
}
313+
```
314+
315+
2. 遍历数组，如果`target - num`在`Map`中，返回。反之，将`num`加入`Map`中。
316+
```javascript
317+
let numToIndex=newMap()
318+
319+
for (let i=0; i<nums.length; i++) {
320+
if (numToIndex.has(target- nums[i])) {// 1
321+
return [numToIndex.get(target- nums[i]), i]// 2
322+
}
323+
324+
numToIndex.set(nums[i], i)
325+
}
326+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp