leetcode 刷题(1)--- 两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

  给定 nums = [2, 7, 11, 15], target = 9

  因为 nums[0] + nums[1] = 2 + 7 = 9

  所以返回 [0, 1]

应该注意问题:1.数组是否可以改变原来顺序。2.同样的元素是否可以被重复利用。3.是否存在多组解。4.时间复杂度。5.空间复杂度。

方法1:利用 map,时间复杂度 O(n),空间复杂度 O(n)。

class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> result;
    map<int, int> num;
    for (int i = 0; i<nums.size(); ++i){
      if (num.find(target-nums[i]) != num.end()){
        result.push_back(num[nums[i]]);
        result.push_back(i);
      }
      else{
        num[nums[i]]=1;
      }
    }
    return result;
  }
};

方法2:先排序,然后利用左右两个指针遍历,如果相加之和大于目标值则右指针前移,如果小于则左指针后移,时间复杂度 O(nlogn),空间复杂度 O(1)

上一篇:Log4j2升级jar包冲突问题


下一篇:Codeforces Round #321 (Div. 2) Kefa and Company 二分