# Leetcode

## two sum

[TOC]

### 暴力解

Feature: Brute-force

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

時間複雜度為O(n^2^) , 一個一個加起來再比對，最基本解法。

---

### hashmap

Feature: hashMap

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashMap;
        vector<int> ans; 
        for(int i = 0 ; i < nums.size() ; i++){
            int rest = target - nums[i];
            if(hashMap.find(rest) != hashMap.end()){
                ans.push_back(i);
                ans.push_back(hashMap[rest]);
                break;
            }
            else{
                hashMap[nums[i]] = i;
            }
        }
        return ans;
    }
};

建立hash map，因題目有說是唯一解，不會重複使用元素，
所以若能找到在hash_map中找到target-nums[i] 就是找到答案，
若沒找到就把nums[i]加入hash map，
這樣一來時間複雜度就降到**O(n)**