LeetCode1.两数之和-创新互联

题目链接：https://leetcode.cn/problems/two-sum/

思路如下：

从前往后遍历 n u m s [   ] nums[\ ] nums[ ] 数组，对于每个元素 n u m s [ i ] nums[i] nums[i] 我们做两件事：

• 判断 t a r g e t − n u m s [ i ] target - nums[i] target−nums[i] 是否在哈希表中；
• 将 n u m s [ i ] nums[i] nums[i] 插入哈希表中；

由于数据保证有且仅有一组解，假设是 { j , i }   ( j < i ) \left\{ j, i \right\}\ (jj,i} (j

由于只扫描一遍，且哈希表unordered_map的插入和查询操作的复杂度是 O ( 1 ) O(1) O(1)，所以总时间复杂度是 O ( n ) O(n) O(n)。

C++代码如下：

class Solution {public:
    vectortwoSum(vector& nums, int target) {int n = nums.size();
        unordered_maphash;
        for (int i = 0; i< n; i++) {int x = target - nums[i];
            if (hash.count(x)) return {hash[x], i};
            hash[nums[i]] = i;
        }
        return {};
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧