Joyce' Blog
0%

Two Sum

发表于 更新于
Description:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

本来想找道很简单的题目消磨时间，出了好几次错之后，觉得自己的水平真是，惨不忍睹——不仅至今没有处理异常的习惯，连整数数组里面出现负数的情况都没有考虑……

最先想到的是直接遍历的方法，时间复杂度为O(n^2)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> a;
		for(int i=0;i<nums.size();i++)
        {
            int x = target - nums[i];
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (nums[j] == x)
                {
                    a.push_back(i);
                    a.push_back(j);
                    return a;
                }
            }
        }
       throw "Bad Input !";
	}
};