LeetCode 1

概述

• https://leetcode-cn.com/problems/two-sum/
• 给定一个整数数组和一个target,从数组中选择两个相加等于target的值，返回选择的两个的数组下标
• 同一个元素不能被重复选,且只会有一个结果

思路

• 返回下标，说明不能排序，那么不能使用多指针法；

• 题目只是要求，同一个元素不能被重复选，并没有说最终结果中不能有重复的元素，所以可以使用哈希法或find()函数

  //方法一 find()函数找，时间复杂度高
  vector<int> twoSum(vector<int>& nums, int target) {
      for(int i=0;i<nums.size();i++){
          int temp=target-nums[i];
          auto index=find(nums.begin(),nums.end(),temp);
          int t=index-nums.begin();
          if(index!=nums.end()&&t!=i){	//确保不是同一元素
              return {i,t};
          }
      }
      return {0,0};
  	}

  //方法二 哈希法
  vector<int> twoSum(vector<int>& nums, int target) {
      unordered_map<int,int> mp;
      for(int i=0;i<nums.size();i++){
          mp[nums[i]]=i+1;    //记录索引，这题题目明确说 只有一个答案才可以这样做的
      }
      for(int i=0;i<nums.size();i++){
          int temp=mp[target-nums[i]];
          if(temp!=0&&temp-1!=i){     /
              return {i,temp-1};
          }
      }
      return {};
  }

   /*官方题解 哈希
   注意和自己的方法二的不同，方法二是针对此题明确一个答案才可以那样。
   因为法二在记录索引是，相同的nums[i]的值会被覆盖，之会存在一个索引。
   但是，因为只有一个答案，所以如果有相同的值，那么要么是用不到的，要么一定是两个相同值就是最终的答案；否则不可能只有一个解
   */
  vector<int> twoSum(vector<int>& nums, int target) {
          unordered_map<int, int> hashtable;
          for (int i = 0; i < nums.size(); ++i) {
              auto it = hashtable.find(target - nums[i]);
              if (it != hashtable.end()) {
                  return {it->second, i};
              }
              hashtable[nums[i]] = i;
          }
          return {};
      }