Loading...
墨滴

高性能架构探索

2021/10/09  阅读:31  主题:简

两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例一:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例二:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例三:

输入:nums = [3,3], target = 6
输出:[0,1]

解决方案

看到此题目的第一眼,很简单,不就是从数组中找两个和等于一个给定值的两个数么。方案如下:

双重循环(TLE)

vector<int> twoSum(vector<int>& nums, int target) {
  for (int i = 0; i < nums.size(); ++i) {
    for (int j = i + 1; j < nums.size(); ++j) {
      if (nums[i] + nums[j] == target) {
        return {i, j}; // 找到了,则返回
      }
    }
  }
  
  return {}; // 未找到,返回空
}

代码很简单,

  • 第一层循环遍历所有的数
  • 第二层循环,判断数组中剩下的数是否满足要求

时间复杂度 O(n2),空间复杂度O(1) 提交,TLE,那么有没有办法来进行优化呢?

哈希

在上面的解法中,我们对于每一个数,都去循环遍历数组中其他数,看看是否存在与其之和相加等于target的数。我们不妨换个思路,对第二个for循环进行优化:

将每个数都存储到hash中,这样判断是否在hash中就可以了

代码如下:

vector<int> twoSum(vector<int>& nums, int target) {
  std::unordered_map<int, int> m; // key为值,value为在数组中的索引
  for (int i = 0; i < nums.size(); ++i) {
    m[nums[i]] = i; // 存储kv对
  }
  
  for (int i = 0; i < nums.size(); ++i) {
    if (m.count(target - nums[i]) && m[target - nums[i]] != i) { // 判断是否存在该数
      return {i, m[target - nums[i]]}; 
    }
  }
  
  return {}; // 未找到
}

高性能架构探索

2021/10/09  阅读:31  主题:简

作者介绍

高性能架构探索