前往 leader.me 打造你的开发者个人IP →

访问原文链接：1. 两数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解，体验更佳！

力扣链接：1. 两数之和, 难度等级：简单。

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

输入: nums = [2,7,11,15], target = 9

输出: [0,1]

解释: 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

输入: nums = [3,2,4], target = 6

输出: [1,2]

输入: nums = [3,3], target = 6

输出: [0,1]

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

1. 暴力解法的时间复杂度为O(n**2)，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据和情况决定left += 1还是right -= 1。

2. 对数值数组排序后，想知道某个数值对应的原来的索引下标，有两种方案：

- 方案1：在排序时带上索引下标，即排序的对象是元组`(num, index)`的数组。这个技术**一定要掌握**，许多题目都会用到。
- 方案2：使用index() 查找，已经放到另外一个题解中讲解。

• 时间复杂度: O(N * log N).
• 空间复杂度: O(N).

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_index_list = [(num, i) for i, num in enumerate(nums)]
        num_index_list.sort()

        left = 0
        right = len(nums) - 1

        while left < right:
            sum_ = num_index_list[left][0] + num_index_list[right][0]
            
            if sum_ == target:
                return [num_index_list[left][1], num_index_list[right][1]]

            if sum_ < target:
                left += 1
                continue

            right -= 1

// Welcome to create a PR to complete the code of this language, thanks!

1. Map中，key是num，value是数组index。
2. 遍历数组，如果target - num在Map中，返回。反之，将num加入Map中。

1. Map中，key是num，value是数组index。

   let numToIndex = new Map()
   
   for (let i = 0; i < nums.length; i++) {
     numToIndex.set(nums[i], i)
   }

2. 遍历数组，如果target - num在Map中，返回。反之，将num加入Map中。

   let numToIndex = new Map()
   
   for (let i = 0; i < nums.length; i++) {
     if (numToIndex.has(target - nums[i])) { // 1
       return [numToIndex.get(target - nums[i]), i] // 2
     }
   
     numToIndex.set(nums[i], i)
   }

• 时间复杂度: O(N).
• 空间复杂度: O(N).

class Solution {
    public int[] twoSum(int[] nums, int target) {
        var numToIndex = new HashMap<Integer, Integer>();
  
        for (var i = 0; i < nums.length; i++) {
            if (numToIndex.containsKey(target - nums[i])) {
                return new int[]{numToIndex.get(target - nums[i]), i};
            }

            numToIndex.put(nums[i], i);
        }

        return null;
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        
        for i, num in enumerate(nums):
            if target - num in num_to_index:
                return [num_to_index[target - num], i]

            num_to_index[num] = i

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num_to_index;
  
        for (auto i = 0; i < nums.size(); i++) {
            if (num_to_index.contains(target - nums[i])) {
                return {num_to_index[target - nums[i]], i};
            }

            num_to_index[nums[i]] = i;
        }

        return {};
    }
};

var twoSum = function (nums, target) {
  let numToIndex = new Map()
  
  for (let i = 0; i < nums.length; i++) {
    if (numToIndex.has(target - nums[i])) {
      return [numToIndex.get(target - nums[i]), i]
    }

    numToIndex.set(nums[i], i)
  }
};

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var numToIndex = new Dictionary<int, int>();
  
        for (int i = 0; i < nums.Length; i++) {
            if (numToIndex.ContainsKey(target - nums[i])) {
                return [numToIndex[target - nums[i]], i];
            }

            numToIndex[nums[i]] = i;
        }

        return null;
    }
}

func twoSum(nums []int, target int) []int {
    numToIndex := map[int]int{}

    for i, num := range nums {
        if index, ok := numToIndex[target - num]; ok {
            return []int{index, i}
        }

        numToIndex[num] = i
    }

    return nil
}

def two_sum(nums, target)
  num_to_index = {}

  nums.each_with_index do |num, i|
    if num_to_index.key?(target - num)
      return [num_to_index[target - num], i]
    end

    num_to_index[num] = i
  end
end

// Welcome to create a PR to complete the code of this language, thanks!

1. 暴力解法的时间复杂度为O(n^2)，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据和情况决定left += 1还是right -= 1。
2. 找出了两个值后，需要用index()方法去找值对应的index。

• 时间复杂度: O(N * log N).
• 空间复杂度: O(N).

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        original_nums = nums.copy()
        nums.sort()

        left = 0
        right = len(nums) - 1

        while left < right:
            sum_ = nums[left] + nums[right]

            if sum_ == target:
                break

            if sum_ < target:
                left += 1
                continue

            right -= 1

        return [
            original_nums.index(nums[left]),
            len(nums) - 1 - original_nums[::-1].index(nums[right])
        ]

// Welcome to create a PR to complete the code of this language, thanks!

🚀 打造你的开发者个人IP

掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。

我的另一个项目 leader.me —— 专为程序员打造的“全能型”个人品牌展示平台。

三位一体（All-In-One）的职场利器：

• 📄 简历 + 作品集 + 博客： 将你的 GitHub 项目、技术心得与职场经历完美融合。
• 🌐 永久免费自定义域名： 支持绑定你自己的独立域名，且该功能永久免费。
• ✨ 顶级行业子域名： 提供 name.leader.me，极具职业含金量的专属域名。

立即前往 leader.me 打造你的个人品牌 →

访问原文链接：1. 两数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解，体验更佳！

GitHub 仓库: leetcode-python-java.