[LeetCode] 1 Two Sum

原题地址：

https://leetcode.com/problems/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.

Example:

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

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

解法：

这是很简单的一道题目，也是LeetCode的第一道题，首先想到的肯定是最基本的暴力方法，用两层循环就解决了。

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

这个算法的时间复杂度为O(n^2)，假如不break的话，是会TLE的。

实际上有很多时间复杂度为O(n)的解法，用空间去换时间。用C++里面的容器来做，十分简单（下面的代码来自于：http://www.cnblogs.com/grandyang/p/4130379.html）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); ++i) {
            int t = target - nums[i];
            if (m.count(t) && m[t] != i) {
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

还有一种做法，先复制一个原来的数组，再将原来的数组排序，用i和j从两端开始，找出符合的结果，假如nums[i] + nums[j] < target，i增加；假如nums[i] + nums[j] > target，j减少。nums[i] + nums[j] == target时，nums[i]和nums[j]就是所求的两个值，但是结果要的是原数组的下标，因此要再遍历一遍原数组，找出下标：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        vector<int> copy = nums;
        sort(nums.begin(), nums.end());
        int num1, num2;
        int i = 0, j = nums.size() - 1;
        while (i <= j) {
            if (nums[i] + nums[j] == target) {
                break;
            }
            else if (nums[i] + nums[j] < target) {
                i++;
            }
            else {
                j--;
            }
        }
        for (int k = 0; k < copy.size(); k++) {
            if (copy[k] == nums[i] || copy[k] == nums[j]) res.push_back(k);
        }
        return res;
    }
};