暴力

直接for循环遍历两边，相加判断是否等于target值，如果相等就加入下标。

时间复杂度是$O(N^2)$，两个for循环

代码

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;
    }
};

---

哈希表

哈希表查找的时间复杂度是$O(1)$，那么我们可以通过target - nums[i]去查找对应下标，通过一次遍历，因为根据题目要求，只要一组答案，那么找到可以直接返回，否则把nums[i] 的下标通过哈希表存储起来。

代码

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

时间复杂度$O(N)$，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 $O(1)$去寻找 target - x。

1. 两数之和 - 力扣（LeetCode）