1. Two Sum

1. Two Sum

难度: Easy

刷题内容

原题连接

内容描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路 1
- 时间复杂度: O(N^2)- 空间复杂度: O(1)

暴力解法,两轮遍历

第一轮取出indexi的数num1,第二轮取出一个更靠后的indexj的数num2

  • 因为如果第二轮取得num1之前的数的话,其实我们之前就已经考虑过这种情况了
  • 如果第二轮再次取num1的话,不符合题目要求

题目只要求找到一种,所以一旦找到直接返回

时间复杂度中的N代表的是nums列表的长度

beats 27.6%

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: 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
- 时间复杂度: O(N)- 空间复杂度: O(N)

上面的思路1时间复杂度太高了,典型的加快时间的方法有牺牲空间换取时间

top Created with Sketch.