LeetCode-1 两数之和---Python代码实现及详解

不念不忘少年蓝@ 2024-04-17 06:00 31阅读 0赞

### 题目： ###

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

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

示例:
        给定 nums = [2, 7, 11, 15], target = 9
    
        因为 nums[0] + nums[1] = 2 + 7 = 9
        所以返回 [0, 1]

### **思路：** ###

**        首先要注意题目的要求读懂题意，不能重复使用相同元素，假如 target=4时不能重复使用2。数组中两个数相加等于目标值的只有一种答案。你可能会想到用到冒泡算法的思想。**

**方法一：使用冒泡冒泡算法思想+切片。（推荐） **index() 函数用于从列表中找出某个值第一个匹配项的索引位置。

复杂度分析：时间复杂度：O(n)空间复杂度：O(1)

class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            # 使用切片方法
            for i in range(len(nums)):
                if target-nums[i] in nums[i+1:]:
                    return [i, nums.index(target-nums[i], i+1)]

**方法二：使用暴力解法**

复杂度分析：时间复杂度：O(n^2)空间复杂度：O(1)

class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
           
            # 使用暴力解法
            length = len(nums)
            for i in range(length):
                for j in range(i+1, length):
                    if nums[i] + nums[j] == target:
                        return [i, j]