1. 兩數(shù)之和(Two Sum)

題目難度： 簡單

給定一個整數(shù)數(shù)組和一個目標值，找出數(shù)組中和為目標值的兩個數(shù)。

你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[**0**] + nums[**1**] = 2 + 7 = 9
所以返回 [**0, 1**]

Solution

Language: C++

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

感悟

目前因為對數(shù)據(jù)結(jié)構(gòu)和算法方面的知識已經(jīng)忘了，以后學到之后會去添加哈希表的算法。

暴力遍歷的方法：

• 時間復(fù)雜度：O(n^2)， 對于每個元素，我們試圖通過遍歷數(shù)組的其余部分來尋找它所對應(yīng)的目標元素，這將耗費 O(n) 的時間。因此時間復(fù)雜度為 O(n^2)。
• 空間復(fù)雜度：O(1)。

最開始寫這道題的時候犯了一個致命的錯誤，因為這樣的遍歷讓我想到了冒泡排序，直接套了一個模板上去，發(fā)現(xiàn)報了很多的錯，以后不能這樣先入為主，還是應(yīng)該仔細思考過后再進行解答。