--

leetcode 001: two sum

https://leetcode.com/problems/two-sum/

---

---

problem:

---

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

---

---

start code (c++)

---

class Solution {
public:
    vector twoSum(vector& nums, int target) {
    }   
};

---

---

solution 1:

---

最简单的是对每一个元素，去查看他的对应的元素是不是在 vec 里面
这里 i1 表示返回的第一个 index （较小的哪一个），i2 表示返回的第二个 index （较大的那一个），i2 的遍历可以从 i1 + 1 开始。
算法复杂度 n^2

---

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        int i1, i2;
        int found = 0;
        for (i1 = 0; i1 < nums.size(); i1 ++){
            int val1 = nums[i1];
            int val2 = target - val1;
            for (i2 = i1+1; i2 < nums.size(); i2 ++){
                if (nums[i2] == val2){
                    found = 1;
                    break;
                }
            }
            if (found == 1)
                break;
        }
        vector solution;
        solution.push_back(i1);
        solution.push_back(i2);
        return solution;
    }
};

---

solution 2:

---

我们可以对数组排序，然后从两边往中间推进。
具体来讲，对于一个从大到小排好序的数组，从最左边取一个数 a1 (最小的)，从最右边取一个数 b1 (最大的)。
如果 a1 + b1 > target, 那么不可能存在一个数，使之和 b1 相加等于 target, 丢弃 b1，然后继续判断剩下的最大的数和最小的数。
如果 a1 + b1 < target, 那么不可能存在一个数，使之和 a1 相加等于 target, 丢弃 a1，然后继续判断剩下的最大的数和最小的数。
如果 a1 + b1 = target, 那么 a1 和 b1 就是我们的求解。
这样遍历一遍的时间复杂度是线性的为 n，但是问题麻烦的地方在于 排序，以及，要求返回索引号，我们在排序之后失去了数字的原始索引号，
所以需要额外的空间保存排序之后的序列。
另外一个需要注意的情况是，如果target 是6，里面有两个 3，我们需要返回这两个不同位置的 3 的 index

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector nums_sorted = nums;
        std::sort(nums_sorted.begin(), nums_sorted.end());
        int i1 = 0;
        int i2 = nums_sorted.size() -1;
        while (i2 > i1){
            int sum = nums_sorted[i1] + nums_sorted[i2];
            if (sum == target)
                break;
            if (sum > target)
                i2 --;
            else
                i1 ++;
        }
        int val1 = nums_sorted[i1];
        int val2 = nums_sorted[i2];
        
        i1 = -1;
        i2 = -1;
        for (int i = 0; i < nums.size(); i ++){
            if (i1 > -1 && i2 > -1)
                break;
            
            if (i1 == -1 && nums[i] == val1)
                i1 = i;
            else if (i2 == -1 && nums[i] == val2)
                i2 = i;
        }
        vector solution;
        solution.push_back(i1);
        solution.push_back(i2);
        return solution;
    }
};

---

solution 3
最后一种方法用到了 hash table 或者 map, 利用hash table 他的优点在于插入和判断只要常数的时间
或者我们用 map，用 val => index 来匹配，map 的背后是红黑树结构。
我们只用了一次遍历来查找并且构建 这个 map，每次查找或者插入 一个元素的用时是 lg N, 整体复杂度为 NlgN 但是需要占用额外的两倍以上的空间。（分别用来保存 val，idx，以及一些 map 内部的指针）

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        # first check if there's 2 target/2 element in the vector
        vector solution;
        map map_val_idx;
        for (int idx1 = 0; idx1 < nums.size(); idx1 ++){
            int val1 = nums[idx1];
            int val2 = target - val1;
            map::iterator it = map_val_idx.find(val2);
            if (it != map_val_idx.end()){
                solution.push_back(idx1);
                solution.push_back(it->second);
                break;
            }else{
                map_val_idx.insert(std::pair(val1, idx1) );
            }
        }
        return solution;
    }
};