两数之和

暴力解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        

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

哈希表

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for k, v in enumerate(nums):
            tmp = target - v
            if tmp in hashtable:
                return [hashtable[tmp],k]
            else:
                hashtable[v] = k

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash_table;
        for (int i = 0; i < nums.size(); i++) {
            auto it = hash_table.find(nums[i]);
            if (it == hash_table.end()){
                hash_table[target-nums[i]] = i;
            }else{
                return std::vector<int>{it->second, i};
            }
        }
        return {};
    }
};