力扣题库_#1.两数之和

题目

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

你可以假设每种输入只会对应一个答案.但是,你不能重复利用这个数组中同样的元素.

实例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣(LeetCode)

解题思路

暴力破解
首先取列表的长度l = len(nums)
使用两层for循环,遍历下标i j = i + 1,
使用if条件判断,当将i j对应的元素不相等且二者的和等于target的值时返回由i j组成的List

Python代码

def twoSum(nums, target):
    l = len(nums)
    for i in range(l):
        for j in range(i + 1, l):
            if nums[i] != nums[j] and target == (nums[i] + nums[j]):
                return [i, j]
    return False

情况1

nums = [5, 3, 2, 4, 15]
target = 6

twoSum(nums, target)

情况2

nums = [5, 3, 3, 11, 15]
target = 6

twoSum(nums, target)

注:使用Jupyder Notebook编辑,可以直接输出,如果写成.py脚本文件自行添加print()语句

输出结果

情况1

[2, 3]

情况2

False

复杂度分析

时间复杂度: $\omicron(n^2)$ ,对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 $\omicron(n)$ 的时间.因此时间复杂度为 $\omicron(n^2)$ .
空间复杂度: $\omicron(1)$ .