【数组 &双指针】Leecode-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]

【题解】

    题解1：

• 思路

         直接两次for循环遍历

• 复杂度

         时间复杂度：O(n2)，空间复杂度：O(1)

• 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> 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(nlogn)，空间复杂度：O(n)

• 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums = sorted(zip(nums, range(len(nums))))
        left = 0
        right = len(nums)-1
        while left<right:
            if nums[left][0]+nums[right][0] < target:
                left +=1
            elif nums[left][0]+nums[right][0] > target:
                right -= 1
            else:
                return [nums[left][1],nums[right][1]]

  题解3：

• 思路：

       一次遍历数组，将遍历后的值放到字典中，右下表在字典中查找

• 复杂度

         时间复杂度：O(n)，空间复杂度：O(n)

• 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        has = {}
        for i, n in enumerate(nums):
            if has.get(target - n) is not None:
                return [i,has.get(target - n)]
            has[n] = i