Two Sum

题目描述:

原题链接

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

题目大意:

给一个数组,找出数组中两个元素的和为某一个给定值。

解法一:

最直观的解法就是两重循环,不多说,时间复杂度最坏为 O(n^2),空间复杂度为O(1).

Leetcode OJ会Time Limit Exceeded。

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> r ;
            for(int i = 0; i < nums.size(); i++){
                for(int j = i + 1; j < nums.size(); j++){
                    if(nums[i] + nums[j] == target){
                        r.push_back(i);
                        r.push_back(j);  
                        break; 
                    }
                }
            }
            return r;
        }
};

解法二:

先排序,然后从两头往中间查找,直到找到为止,时间复杂度为O(nlogn), 因为要求的是数组的下标,所以要在排序之前保存数组的下标,所以空间复杂度为O(n).

struct Node{
    int val; 
    int id;
    Node(int val,int id) : val(val), id(id){}
};

bool cmp(const Node & left, const Node & right){
    return left.val < right.val;
}

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> r ;
            vector<Node> nodes;
            for(int i = 0; i < nums.size(); i++){
                Node item(nums[i], i);
                nodes.push_back(item);
            }
            sort(nodes.begin(),nodes.end(),cmp);

            int i = 0; 
            int j = nodes.size() - 1;

            while(i < j){
                int sum = nodes[i].val + nodes[j].val;
                if(sum > target){
                    j--;
                    continue;
                }

                if(sum < target){
                    i++; 
                    continue;
                }

                if(nodes[i].id > nodes[j].id){
                    r.push_back(nodes[j].id + 1);
                    r.push_back(nodes[i].id + 1); 
                }else{
                    r.push_back(nodes[i].id + 1);
                    r.push_back(nodes[j].id + 1);   
                }

                break;
            }

            return r;
        }
};    

解法三:

使用hash表,键为数组的值,值为下标。每遍历到一个数,则在表中保查看是否有target减去这个值,如果没有,则把这个值以及对应的下标存入hash表。时间复杂度为O(n),空间复杂度为O(n)

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> r ;
            unordered_map<int,int> hmap;
            for(int i = 0; i < nums.size(); i++){
                if(hmap.find(target - nums[i]) != hmap.end()){
                    r.push_back(hmap[target - nums[i]] + 1);
                    r.push_back(i + 1);
                    return r;
                }else{
                    hmap[nums[i]] = i;
                }
            }

            return r;
        }
};

Comments !

个人链接