1. 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.

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

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

Solution

给定数组nums和target，求数组中两数（要index）之和等于target，easy级别。

• 暴力搜索
  两层循环遍历数组，求得两数之和等于target，时间O(n²)，空间O(1)，亲测能够AC

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> retVec(2,-1);
    for (int i = 0; i < nums.size() - 1; ++i) {
        for (int j = i + 1; j < len; ++j) {
            if (nums[i] + nums[j] == target) {
                retVec[0] = i;
                retVec[1] = j;
                break;
            } 
        }
    }
    return retVec;
}

• 前后夹逼法（排序+贪心）
  对于O(n²)的复杂度，是否存在优化的可能？我们假定数组已经assending有序，借助于贪心算法惯用的双指针思路，分别指向begin=0和end=len-1的位置，如果两数之和>target，则只能减小end才有可能找到；如果两数之和<target，只能增大begin。
  但是题目要求返回的是index，因此排序时必须保证索引信息不丢失，只能自定义结构体和排序。
  排序O(nlogn)，夹逼O(n)，整体时间复杂度O(nlogn)，空间O(n)，能够AC

struct MyNode {
    int val;
    int index;
    MyNode(int x, int y): val(x),index(y){}
    bool operator < (const MyNode& rhs) const {  
        return val < rhs.val;
    }
};
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> retVec(2,-1);
        vector<MyNode> nodeVec;
        for (int i = 0; i < nums.size(); ++i) {
            MyNode node(nums[i], i);
            nodeVec.push_back(node);
        }
        sort(nodeVec.begin(), nodeVec.end());
        int begin = 0, end = nodeVec.size() - 1;
        while (begin < end) {
            if (nodeVec[begin].val + nodeVec[end].val < target) {
                begin++;
            } else if (nodeVec[begin].val + nodeVec[end].val > target) {
                end--;
            } else {
                retVec[0] = nodeVec[begin].index;
                retVec[1] = nodeVec[end].index;
                break;
            }
        }
        return retVec;
    }
};

• 极速查找（借助map/hashMap）
  很多时候，我们需要在一堆数中找一个数，使用数组遍历O(n)复杂度，但其实借助于map或者hashMap数据结构，可以将复杂度降低到O(logn)，甚至O(1)
  整体时间复杂度O(n)，空间O(n)，可以AC

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ret{-1, -1};
    unordered_map<int, int> myHash;
    for(int i = 0; i < nums.size(); ++i) {
        if (myHash.find(target - nums[i]) != myHash.end()) {
            ret[0] = myHash[target - nums[i]];
            ret[1] = i;
            break;
        }
        myHash[nums[i]] = i;
    }
    return ret；
}