8000 edit 001 solution · Mowmowj/leetcode@4b43c87 · GitHub
[go: up one dir, main page]

Skip to content

Commit 4b43c87

Browse files
committed
edit 001 solution
1 parent 1d16e37 commit 4b43c87

File tree

2 files changed

+13
-30
lines changed

2 files changed

+13
-30
lines changed

problems/001. Two Sum/README.md

Lines changed: 13 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,10 @@
1-
# 1. Two Sum
1+
# #1 暴力搜索[AC]
22

3-
## Description
3+
## 思路
44

5-
```
6-
Difficulty: Easy
7-
Total Accepted:580.8K
8-
Total Submissions:1.7M
9-
Contributor: LeetCode
10-
```
11-
12-
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
13-
14-
You may assume that each input would have exactly one solution, and you may not use the same element twice.
5+
最直接的想法就是遍历所有解空间,然后判断遍历到的两个值的和是不是等于我们要求的值。这里使用了穷举法,也就是遍历了所有解空间,然后得到所求的解, 这应该是最直接的方式了,所以时间复杂度也相对较高。
156

16-
**Expample:**
17-
18-
```
19-
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,
20-
return [0, 1].
21-
```
22-
23-
***
24-
25-
## Solution1
26-
27-
最直接的想法就是遍历所有解空间,然后判断遍历到的两个值的和是不是等于我们要求的值。这里使用了穷举法,也就是遍历了所有解空间,然后得到所求的解, 这应该是最直接的方式了,所以时间复杂度也相对较高。
7+
## 算法
288

299
```java
3010
public class Solution {
@@ -41,16 +21,22 @@ public class Solution {
4121
}
4222
```
4323

44-
时间复杂度为 : $O(n^2).$
24+
## 性能分析
4525

26+
### 时间复杂度
4627

28+
$O(n^2)$
4729

48-
## Solution2
30+
# #2 时空互换[AC]
4931

50-
这里的改进方式主要的思想是, 时空互换 ,通过建立一个HashTable或者HashMap来存储数组中的值以及其对应的位置,也就是说将数组元素的值当做Key,位置当做Value。相应的,我们对问题进行转化,加法转化为减法,什么意思呢,求解nums[i] + num[j] == target, 满足这个条件的 i j。我们转化为 nums[i] = target - nums[j],也就是我们固定一个值 nums[j], 通过条件联立(减法),去求解另一个值,而减法得到的值正好可以作为Hash的Key去搜索,该搜索的时间复杂度为O(1),所以我们只需要一次遍历数组,每次遍历的时候去搜索target - nums[j]即可。
32+
## 思路
33+
34+
这里的改进方式主要的思想是, 时空互换 ,通过建立一个HashTable或者HashMap来存储数组中的值以及其对应的位置,也就是说将数组元素的值当做Key,位置当做Value。相应的,我们对问题进行转化,加法转化为减法,什么意思呢,求解nums[i] + num[j] == target, 满足这个条件的 i j。我们转化为 nums[i] = target - nums[j],也就是我们固定一个值 nums[j], 通过条件联立(减法),去求解另一个值,而减法得到的值正好可以作为Hash的Key去搜索,该搜索的时间复杂度为O(1),所以我们只需要一次遍历数组,每次遍历的时候去搜索target - nums[j]即可。
5135

5236
![](http://p6sh0jwf6.bkt.clouddn.com/2018-07-22-033950.jpg)
5337

38+
## 算法
39+
5440
```java
5541

5642
public int[] twoSum(int[] numbers, int target) {
@@ -68,6 +54,3 @@ public int[] twoSum(int[] numbers, int target) {
6854
}
6955
```
7056

71-
***
72-
73-
**enjoy life, coding now! :D**
-244 KB
Binary file not shown.

0 commit comments

Comments
 (0)
0