LeetCode--Two Sum

发表于 | 分类于 |

题目描述：

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.

样例：

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题意：

给你一个 int 类型的数组，找到数组中的两个数字，相加的和为题目中给出的特定目标，并返回这两个数字在数组中的下标，注意：同样的数字不能重用。

思路：

可以换个角度来考虑问题，如果给定的数组是已排序的数组，那么就可以设定 left 和 right 两个指针，如果这两个数字的和比 target 要大，那么就 right – ，否则 left ++。这样排序数组需要O(N * logN)，找和的过程需要O(N)。

这里附上我刚刚过的代码：

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
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> num = nums;
        std::sort(num.begin(), num.end());
        
        int length = nums.size();
        int left = 0;
        int right = length - 1;
        int sum = 0;
        
        vector<int> index;
        
        while(left < right) {
        	sum = num[left] + num[right];
        	
            if(sum == target) {
            	for(int i = 0; i < length; ++i) {
            		if(nums[i] == num[left]) index.push_back(i);
            		else if(nums[i] == num[right]) index.push_back(i);
            		if(index.size() == 2) break;
            	}
                break;
            }
            else if(sum > target) --right;
            else ++left;
        }
        
        return index;

    }
};

Runtime：4ms Memory：N/A

faster than 100.00%

然后其他道友们是这样写的，我觉得写的真的超级简洁，感觉超棒.jpg

其实蚊子觉得思路是一样的，但是就是写起来感觉超简洁，超喜欢.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        std::unordered_map<int, int> num2id;
        for(int i=0; i < nums.size(); i++)
        {
            int res = target - nums[i];
            auto it = num2id.find(res);
            if(it != num2id.end()) return vector<int>{it->second, i};
            num2id[ nums[i] ] = i;
        }
        
        return vector<int>();
    }
};

Runtime：12ms Memory：10.1MB

faster than 93.91%