当前位置:   article > 正文

LeetCode 1. Two Sum 解题报告_ector twosum(vector& nums, int target

ector twosum(vector& nums, int target
题意:
数组nums中,有两个元素的和是target,找出这两个元素的位置。

思路:
维护一个map,用数组的元素的值做key,用元素的位置做value。遍历nums,对每个num来说,如果map[target - num] 有值的话,就返回map[target - num]和num的位置,如果没有找到的话,就把num插入到map中,map[num] = index。时间复杂度O(nlogn)。

C++ Code:

  1. class Solution {
  2. public:
  3. vector<int> twoSum(vector<int>& nums, int target) {
  4. std::map<int, int> map;
  5. for(int i = 0; i < nums.size(); i++)
  6. {
  7. if(map.find(target - nums[i]) != map.end())
  8. {
  9. std::vector<int> result{map[target - nums[i]], i + 1};
  10. return result;
  11. }
  12. map[nums[i]] = i + 1;
  13. }
  14. }
  15. };
Python Code:
  1. class Solution(object):
  2. def twoSum(self, nums, target):
  3. """
  4. :type nums: List[int]
  5. :type target: int
  6. :rtype: List[int]
  7. """
  8. map = {}
  9. for index,num in enumerate(nums):
  10. if target - num in map:
  11. return [map[target - num], index + 1]
  12. map[num] = index + 1
JS Code:

  1. /**
  2. * @param {number[]} nums
  3. * @param {number} target
  4. * @return {number[]}
  5. */
  6. var twoSum = function(nums, target) {
  7. var map = {}
  8. for(i = 0; i < nums.length; i++)
  9. {
  10. if(map.hasOwnProperty(target - nums[i]))
  11. {
  12. return [map[target - nums[i]], i + 1]
  13. }
  14. map[nums[i]] = i + 1
  15. }
  16. };




声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/460981
推荐阅读
相关标签
  

闽ICP备14008679号