FilesExpand file tree

 master

/

001TwoSum.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (44 loc) · 1.04 KB

 master

/

001TwoSum.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (44 loc) · 1.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

#include <vector>

#include <unordered_map>

#include <iostream>

using namespace std;

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> m; //使用map主要原因为搜索时间为O(n)

vector<int> res;

for (int i = 0; i < nums.size(); ++i) {

m[nums[i]] = i; //键值-值的方式索引

}

for (int i = 0; i < nums.size(); ++i) {

int t = target - nums[i];

if (m.count(t) && m[t] != i) { //map容器中的count()方式为寻找对应的键值

res.push_back(i);

res.push_back(m[t]);

break;

}

}

return res;

}

vector<int> twoSum2(vector<int>& nums, int target) { //合并为一个循环

unordered_map<int, int> m;

for (int i = 0; i < nums.size(); ++i) {

if (m.count(target - nums[i])) { //改进之处核心在于一边审阅，一边向数组写入

return{ i, m[target - nums[i]] };

}

m[nums[i]] = i;

}

return{};

}

};

void main()

{

vector<int> nums;

nums.push_back(2);

nums.push_back(7);

nums.push_back(11);

nums.push_back(13);

int target = 9;

Solution solution;

solution.twoSum2(nums, target);

}