kSum问题汇总

Created at 2017-07-20 Updated at 2017-10-17 Category 2017年8月 Tag Leetcode

LeetCode上面有一系列的kSum问题，这里对kSum进行一个总结。

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.

Example:
Given nums = [2, 7, 11, 15], target = 9,

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

题目分析：一开始考虑说排序，然后再从两头向中间靠拢，就可以求出答案了。但是后来发现这题是要求输出下标，而不是数它本身，所以排序的方法就行不通了。所以就考虑使用haspMap的方式。

解法一:
步骤一：先把整个数组进行排序，然后从两端缩进，看想加的和是否为目标数，这个是最常规的想法。这题由于是要输出下标而不是数值本身，所以还要遍历一遍数组找到对应的下标。
代码：

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

解法二：
步骤一：先把所有的数都加入到map当中，因为数组中有重复的数存在，所以就没有办法让map中对应的值为它的下标，到时候直接取出来就行。而是让它的值加一。
步骤二：通过一个循环，把当前数对应的map值减一，然后再调用map判断这个值是否存在，并且它的值是否大于０，如果都满足，则说明找到了答案。
步骤三：这个时候需要根据我们找到的那个答案的值，然后去找对应的下标。

代码：

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 
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        if(nums.size() == 0){
            return res;
        }
        map<int,int> m;
        for(int i = 0; i < nums.size(); i++){
            if(m.find(nums[i]) != m.end()){
                m[nums[i]]++;
            }else{
                m[nums[i]] = 1;
            }
        }//把所有的值都放到map里面去。
        for(int i = 0; i < nums.size(); i++){
            int left = target - nums[i];
            m[nums[i]]--;
			//使用完一次就减一。下面再判断是否大于0，这样子可以防止[3,3]
            if(m.find(left) != m.end() && m[left] > 0){
                res.push_back(i);
                for(int j = i+1; j < nums.size(); j++){
                    if(nums[j] == left){
                        res.push_back(j);
                        break;
                    }
                }
                break;
            }
        }
        return res;
        
    }
    
};

解法三：
看了讨论就会发现同样是用hashmap，但是人家的运行时间可以更快，快了3ms。

直接遍历，如果目标值减去当前值并没有存在map中的时候，就直接把这个值加到map当中，然后map中这个值对应的值就是它的下标。如果找到就直接返回就可以了。

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

kSum问题汇总

Two Sum

Table of Content