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.

---

Solution 1

C++

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

最朴素的解法，枚举每一个对,时间复杂度为o(n²)

Solution 2

C++

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

通过哈希表来存储遍历过的元素的值和对应的索引，每一次遍历都查看是否有target-nums[i]这样的值，有的话答案就出来，这种方式的时间复杂度为o(n)