leetcode-two-sum

问题

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

出处:https://leetcode.com/problems/two-sum/description/

原文大意

给定一个整数数组和一个目标数target,返回数组中两个相加等于target的元素的下标;假设给定的数据中恰巧只有一个解,并且同一个元素不可使用两次.

例如:
给定一个数组nums = [2, 7, 11, 15],target = 9,
因为 2+7 = 9,而2, 7在数组中的下标分别为0,1,所以返回[0,1].

解题思路

1. 暴力求解

看到这道题,就想到用两个for循环遍历两遍,判断两个值相加是否等于target,C++代码如下:

vector<int> twoSum(vector<int>& nums, int target) {
      std::vector<int> r;
        int len = nums.size();
        //遍历一次数组
        for (int i = 0; i < len; ++i)
        {
          bool f = false;
          //再遍历一次数组,让当前值与后面的值全都运算一遍
          for (int j = i+1; j < len; ++j)
          {
            if(nums[i] + nums[j] == target){
              r.push_back(i);
              r.push_back(j);
              f = true;
              break;
            }
          }
          if (f)
          {
            break;
          }
        }
        return r;

由于遍历了两遍,时间复杂度为O(n^2),同时此段代码提交到leetcode,其runtime为119ms,这个时间已经很长了.

2. 哈希表

减少运算时间,寻找优化方法,使用哈希表求解,哈希表查找速度非常快,时间复杂度为O(1),把当前元素的值作为key,其下标作为value,要求两个值之和等于target,即相当于在数组中查找target与当前元素的值之差,于是整个运算只需要循环一遍,其时间复杂度为O(n),C++代码如下:

vector<int> twoSum(vector<int>& nums, int target) {
      int len = nums.size();
      std::vector<int> r;
      std::unordered_map<int, int> hash;

      for (int i = 0; i < len; ++i)
      {
          //计算target与当前元素的差
          int tmp = target - nums[i];
          //判断差值是否在hash中
          if (hash.count(tmp))
          {
              r.push_back(i);
              r.push_back(hash[tmp]);
              return r;
          }
          //若不存在,则将当前元素的下标与其值以key-value形式存入hash中
          hash[nums[i]] = i;
      }
      return r;

此段代码提交到leetcode,其runtime为6ms,运行时间较之暴力求解法明显缩短了.