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

---

开学课业压力好大，已经有两个月没有刷题了，现在开始LeetCode，从#1开始！ 这一题要从一个序列中找出两数之和为target的两个数。因为序列无序，所以能够想到的最简单的方法就是先对数组排序，然后设置头尾两个指针，判断求和情况和target的大小关系。当得到两个数之后，再在原序列中找这两个数的index，注意index1<index2。 完整代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int> nums_copy = nums;
        sort(nums_copy.begin(), nums_copy.end());
        int i = 0, j = nums_copy.size() – 1;
        while (i != j) {
            if (nums_copy[i] + nums_copy[j] == target)
                break;
            else if (nums_copy[i] + nums_copy[j] < target)
                i++;
            else
                j--;
        }
        vector<int> ans(2);
        for (int k = 0; k < nums.size(); k++) {
            if (ans[0] == 0 && nums[k] == nums_copy[i])
                ans[0] = k + 1;
            else if (ans[1] == 0 && nums[k] == nums_copy[j])
                ans[1] = k + 1;
        }
        if (ans[0] > ans[1])
            swap(ans[0], ans[1]);
        return ans;
    }
};

本代码提交AC，用时16MS。
还可以借助hash方法实现O(n)的算法。思路是将nums全部hash存储，然后扫描数组，判断target-nums[i]是否在hash表中。整个运行时间在O(n)。
代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        //map<int, int> nums_index;
        unordered_map<int, int> nums_index; // unordered_map比map快
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); i++) {
            int added = target – nums[i];
            if (nums_index.find(added) != nums_index.end()) {
                ans[0] = nums_index[added];
                ans[1] = i + 1;
                return ans;
            }
            nums_index[nums[i]] = i + 1;
        }
    }
};

本代码提交AC，用时还是16MS。
此题测试数据只有16组，真是太少了，如果数据多的话，相信第二种方法会快很多。