Leetcode #1 - Two Sum

 Leetcode #1 - Two Sum

 ◎ 難度： Easy

 ◎ 題目：

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.


...就是 給你一個整數陣列(向量?)，再給你一個目標數字，你若能由陣列中的任意兩數字相加後 相等於目標數字 就返回這兩個數字在陣列中的順序
  




 ◎ Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 ◎ Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

 ◎ Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]



 ◎ 想法：
題目說明 僅兩數字相加後的結果。所以，設定兩指標 分別指向陣列兩不同數字，逐一試著相加即可


 ◎ C++程式碼：

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

這是最基本的

 ㊣ 另類想法：

既然 我們已經知道  總和target，扣掉 我們目前指向的數之後，我們需要的數字 直接就出來了

我們僅止需要 確認這數字有沒有在陣列中即可，不需要跑一堆迴圈，做一堆加法運算

所以.....

class Solution {
public:
////#define DEBUG 1
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> vi;
        int x,y;
        for (x=0; x<nums.size() -1 ;x++) {
            y=target-nums[x];
            auto z = std::find(nums.begin()+x+1,nums.end(), y );
#ifdef DEBUG 
            cout << "[" << x << "], find:" << y << " -> " << z - nums.begin() << "]\n";
#endif	// DEBUG
            if (z != nums.end()) {
                //cout << "[" << x << "," << z - nums.begin() << "]\n";
                vi.push_back(x);
                vi.push_back(z - nums.begin() );
                break;
            }
        }
        return vi;
    }
};

速度相差近十倍哩