题目

twoSum

算法

• O(n):unordered_map

代码

3.0 测试程序

int main() {
    Solution s;
    vector<int> in;
    int n, t;
    cin >> n;
    while (n--) {
        cin >> t;
        in.push_back(t);
    }
    cin >> t;
    in = s.twoSum(in, t);
    cout << in[0] << ' ' << in[1] << endl;
    return 0;
}

* 哈希

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        if(nums.empty())  return {};
        unordered_map<int, int> m;  
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]] = i;  //m[key]=value

        }
        for (int i = 0; i < nums.size(); ++i) {
            int t = target - nums[i];
            if (m.count(t) && m[t] != i) {
            // count返回出现的次数，没有返回0
            // m[t]!=i， 不可以自身重复
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

* 哈希优化

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        if(nums.empty())  return {};
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            if (m.count(target - nums[i])) {
                return {i, m[target - nums[i]]};
            }
            m[nums[i]] = i;
        }
        return {};
    }
};