leetcode/twoSum.cpp at master · CaesarLXL/leetcode · GitHub

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<vector>
#include<map>
using namespace::std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target);
};

/*
*method(1)-验证通过
*时间复杂度O(n2)
*空间复杂度O(n)
*/
/*vector<int> Solution::twoSum(vector<int>& nums, int target){
	vector<int> indexs;
	for(int i = 0; i < nums.size(); ++i){
		for(int j = i + 1; j < nums.size(); ++j){
			if(nums[i] + nums[j] == target){
				indexs.push_back(i);
				indexs.push_back(j);
				return indexs;
			}
		}
	}
	return indexs;
}*/


/*
*method(2)-验证通过
*时间复杂度O(n)
*空间复杂度O(n)
*/
vector<int> Solution::twoSum(vector<int>& nums, int target){
	map<int, int> imap;
	map<int, int>::iterator iter;
	vector<int> indexs;
	for(int i = 0; i < nums.size(); ++i){
		imap.insert(pair<int, int>(nums[i], i));
	}

	for (int i = 0; i < nums.size(); ++i){
		int val = target - nums[i];
		if (imap.find(val) != imap.end() && imap[val] != i){
			indexs.push_back(i);
			indexs.push_back(imap[val]);
			return indexs;
		}
	}
	return indexs;
}

int main(void){
    int in[] = { 3, 2, 4 };
    vector<int> input(in, in + 3);
    Solution s;
    vector<int> output = s.twoSum(input, 6);
    for (int i = 0; i < output.size(); ++i){
    	cout << output[i] << endl;
    }
    return 0;
}