题目链接

题目描述

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值的那两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入： nums = [3,2,4], target = 6
输出： [1,2]

示例 3：

输入： nums = [3,3], target = 6
输出： [0,1]

提示：

• 2 <= nums.length <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

个人题解

1. C++实现:

   vector<int> twoSum(vector<int>& nums, int target) {
       int n = nums.size();
       vector<int> r;
       int f = 0;
       for(int i = 0; i < n && f == 0; i++) {
           for(int j = i + 1; j < n; j++) {
               if(nums[i] + nums[j] == target) {
                   r.push_back(i);
                   r.push_back(j);
                   f = 1;
                   break;
               }
           }
       }
       return r;
   }
   

2. Python3实现:

   def twoSum(self, nums: List[int], target: int) -> List[int]:
       list = [];
       f = 0;
       for i in range(len(nums)):
           for j in range(i + 1, len(nums)):
               if nums[i] + nums[j] == target:
                   list.append(i);
                   list.append(j);
                   f = 1;
                   break;
           if f == 1: break;
       return list;
   

Leetcode题解

1. Python3代码简化：

   def twoSum(self, nums: List[int], target: int) -> List[int]:
       for i in range(len(nums)):
           for j in range(i + 1, len(nums)):
               if nums[i] + nums[j] == target:
                   return i, j
   

2. 一次循环优化：

   def twoSum(self, nums: List[int], target: int) -> List[int]:
       for i in range(len(nums)):
           if (target - nums[i] in nums) & (i != nums.index(target - nums[i])):
               return i, nums.index(target - nums[i])
   

3. 用字典模拟哈希求解：

   def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i, n in enumerate(nums):
            if target - n in dict:
                return dict[target - n], i
            else:
                dict[n] = i
   

对于一个可迭代的/可遍历的对象(如列表、字符串), enumerate将其组成一个索引序列，利用它可以同时获得索引和值

4. C++哈希解法：

   vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;        
        for(int i = 0; i < nums.size(); i++) {
            if(m.find(target-nums[i]) != m.end()) 
                return {m[target-nums[i]], i};        
            m[nums[i]] = i;
        }
        return {};
    }
   

unordered_map更适合查找类问题，map更适用于有顺序要求问题