LeetCode Python, Java, C++  >  哈希表  >  1. 两数之和  >  已支持 Python  >  GitHub 或 转发

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

    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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 <= 10^4
    • -10^9 <= nums[i] <= 10^9
    • -10^9 <= target <= 10^9
    • 只会存在一个有效答案
    提示 1

    A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

    提示 2

    So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

    提示 3

    The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

    思路
    上一题下一题

    站长 (张健)： 👋

    大家好！我是张健。

    我深知学习算法和找到好工作之间的挑战。因此，除了这个项目，我个人还开发了 leader.me — 这是程序员打造个人IP的终极平台，包含作品集、简历和博客等。
    🚀 掌握算法是基础，而 leader.me 助您完美展示技能，顺利拿到 Offer！

    立即前往 leader.me 打造你的程序员专属个人IP →


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

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

    点击查看答案

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

    复杂度

    时间复杂度

    O(N * log N)

    空间复杂度

    O(N)

    Python # 

    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

    其它语言

    欢迎贡献代码到 LeetCode.blog GitHub -> 1. 两数之和。感谢！

    打造你的开发者个人IP

    🚀 掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。
    我的另一个项目 leader.me —— 专为程序员打造的“全能型”个人品牌展示平台。

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

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

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

    题解2的思路：使用 Map

    站长 (张健)： 👋

    大家好！我是张健。

    我深知学习算法和找到好工作之间的挑战。因此，除了这个项目，我个人还开发了 leader.me — 这是程序员打造个人IP的终极平台，包含作品集、简历和博客等。
    🚀 掌握算法是基础，而 leader.me 助您完美展示技能，顺利拿到 Offer！

    立即前往 leader.me 打造你的程序员专属个人IP →


    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)

    题解语言： Java Python C++ JavaScript C# Go Ruby

    Java # 

    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;
    }
}

    Python # 

    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

    C++ # 

    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 {};
    }
};

    JavaScript # 

    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)
  }
};

    C# # 

    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;
    }
}

    Go # 

    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
}

    Ruby # 

    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
    题解语言： Java Python C++ JavaScript C# Go Ruby

    其它语言

    欢迎贡献代码到 LeetCode.blog GitHub -> 1. 两数之和。感谢！

    打造你的开发者个人IP

    🚀 掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。
    我的另一个项目 leader.me —— 专为程序员打造的“全能型”个人品牌展示平台。

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

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

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

    题解3的思路：双指针2

    站长 (张健)： 👋

    大家好！我是张健。

    我深知学习算法和找到好工作之间的挑战。因此，除了这个项目，我个人还开发了 leader.me — 这是程序员打造个人IP的终极平台，包含作品集、简历和博客等。
    🚀 掌握算法是基础，而 leader.me 助您完美展示技能，顺利拿到 Offer！

    立即前往 leader.me 打造你的程序员专属个人IP →


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

    复杂度

    时间复杂度

    O(N * log N)

    空间复杂度

    O(N)

    Python # 

    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])
        ]

    其它语言

    欢迎贡献代码到 LeetCode.blog GitHub -> 1. 两数之和。感谢！
    上一题下一题

    打造你的开发者个人IP

    🚀 掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。
    我的另一个项目 leader.me —— 专为程序员打造的“全能型”个人品牌展示平台。

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

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

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