LeetCode: 1. Two Sum

题目

原题地址：https://leetcode.com/problems/two-sum/

Given an array of integers nums and and integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1]

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 1 <= nums.length <= 10^5
  • -109 <= nums[i] <= 10^9
  • -109 <= target <= 10^9
  • Only one valid answer exists.

解法

暴力多次遍历查找

暴力多次遍历查找的方法就是，遍历数组用每个元素依次跟数组里的其他元素进行比对，找出答案。

相应实现的 Python 代码类似下面这样：

class Solution(object):
    def twoSum(self, nums, target):
        length = len(nums)

        for current_i, current_value in enumerate(nums):
            another_i_start = current_i + 1

            for another_i, another_v in enumerate(nums[another_i_start: length], another_i_start):
                if current_value + another_v == target:
                    return [current_i, another_i]

一次循环查找

一次循环查找方法的思想就是，把循环过程中遇到的数组元素（比如是 a ）所需的另一个值（target -a）给记下来（记录 target-a 跟 a 的 index 的关系，target-a -> a_index），这样在遍历过程中遇到这个值（target-a）的时候就可以直接反向找到它在找的值的 index （a 的 index）。

相应实现的 Python 代码类似下面这样：

class Solution(object):
    def twoSum(self, nums, target):
        another_value_to_current_index_map = {}

        for current_index, current_value in enumerate(nums):
            another_value = target - current_value

            if current_value in another_value_to_current_index_map:
                pre_index = another_value_to_current_index_map[current_value]
                return [pre_index, current_index]

            another_value_to_current_index_map[another_value] = current_index

Comments