1两数之和2020-07-18

Python

方法一：用 Python 中 list 的相关函数求解
num2 = target - num1，是否也在 list 中，那么就需要运用以下两个方法：
num2 in nums，返回 True 说明有戏
nums.index(num2)，查找 num2 的索引
900ms 13.4MB

def twoSum(nums, target):
    lens = len(nums)
    j=-1
    for i in range(lens):
        if (target - nums[i]) in nums:
            if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):
                continue
            else:
                j = nums.index(target - nums[i],i+1) #index(x,i+1)是从num1后的序列后找num2
                break
    if j>0:
        return [i,j]
    else:
        return []

方法二：
num2 的查找并不需要每次从 nums 查找一遍，只需要从 num1 位置之前或之后查找即可。但为了方便 index 这里选择从 num1 位置之前查找，执行通过，耗时缩短一半多，共 702ms。

def twoSum(nums, target):
    lens = len(nums)
    j=-1
    for i in range(1,lens):
        temp = nums[:i]
        if (target - nums[i]) in temp:
            j = temp.index(target - nums[i])
            break
    if j>=0:
        return [j,i]

方法三：用字典模拟哈希求解
通过哈希来求解，这里通过字典来模拟哈希查询的过程。通过字典的方法，查找效率快很多，执行速度大幅缩短，共 32ms。

def twoSum(nums, target):
    hashmap={}
    for ind,num in enumerate(nums):
        hashmap[num] = ind
    for i,num in enumerate(nums):
        j = hashmap.get(target - num)
        if j is not None and i!=j:
            return [i,j]

方法四：类似方法二，不需要 mun2 不需要在整个 dict 中去查找。可以在 num1 之前的 dict 中查找，因此就只需要一次循环可解决。不过方法四相较于方法三的运行速度没有像方法二相较于方法一的速度提升。运行速度在 70ms 多。

def twoSum(nums, target):
    hashmap={}
    for i,num in enumerate(nums):
        if hashmap.get(target - num) is not None:
            return [i,hashmap.get(target - num)]
        hashmap[num] = i #这句不能放在if语句之前，解决list中有重复值或target-num=num的情况

作者：lao-la-rou-yue-jiao-yue-xiang
链接：https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-jie-fa-by-lao-la-rou-yue-j/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

C++

方法一：暴力
暴力算法时间复杂度O（n²），空间复杂度O（1）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
              for(int j=i+1;j<nums.size();j++){
                  if(nums[i]+nums[j]==target){
                      ans.push_back(i);
                      ans.push_back(j);
                      return ans;
                  }
              }
        }
        return ans;
    }
};

方法二：排序+双指针法
这里先将数组排序好O（nlogn），再利用双指针法遍历一遍O（n）得到结果。
为了保存下标信息另开了一个数组
时间复杂度O（nlogn），空间复杂度O（n）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        vector<int> temp;
        temp=nums;
        int n=temp.size();
       sort(temp.begin(),temp.end());
       int i=0,j=n-1;
       while(i<j){  
           if(temp[i]+temp[j]>target)j--;
          else if(temp[i]+temp[j]<target)i++;
          else break; 
       }
       if(i<j){
      for(int k=0;k<n;k++){
          if(i<n&&nums[k]==temp[i]){
              ans.push_back(k);
              i=n;
          }
         else if(j<n&&nums[k]==temp[j]){
              ans.push_back(k);
              j=n;
          }
          if(i==n&&j==n)return ans;
      }
      }
        return ans;
    }
};

方法三：hash法
利用undered_map数组构造映射，遍历nums[i]时，看target-nums[i]是否存在hash表中即可
时间复杂度O（n），空间复杂度O（n）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
       unordered_map<int,int>hashmap;
       for(int i=0;i<nums.size();i++){
           if(hashmap[target-nums[i]]
          &&hashmap[target-nums[i]]!=i+1){
          //防止利用同个元素
               ans.push_back(i);
               ans.push_back(hashmap[target-nums[i]]-1);
               return ans;
           }
        hashmap[nums[i]]=i+1;
        //将hash表对应下标＋1，防止处理下标为0的情况
       }
      
       return ans;
    }
};

总结：
实际在提交过程中，方法2,3差距不太，1最慢。

作者：yun-yu-chen
链接：https://leetcode-cn.com/problems/two-sum/solution/san-chong-fang-fa-bao-li-shuang-zhi-zhen-ha-xi-san/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最后编辑于：2020.07.18 16:53:36