【刷题笔记1】两数之和

题目来源LeetCode 1.两数之和
本贴为个人日常刷题笔记，有任何问题欢迎随时交流~
该题类别是：数组

一、题目

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

• 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

• 你可以按任意顺序返回答案。

• 进阶：想出一个时间复杂度小于 $O(n^2)$ 的算法

二、提示

• $2\le nums.length\le 10^4$
• $-10^9\le nums[i]\le 10^9$
• $-10^9\le target\le 10^9$
• 只会存在一个有效答案

三、思考

• 两数求和，两两运算，需要两个指针
• 唯一匹配，涉及比较
• nums是无序数组（转成有序如何处理）

四、解法

1. 暴力求解

• 快慢指针遍历，两层变量
• 时间复杂度：$O(n^2)$

class Solution:
    def two_sum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

2. 排序+双指针

• 数组nums先排序
• 左右双指针
• 难度在于下标位置发生改变了，需要用nums.index(value)进行查找
  • sort()复杂度为 $O(nlogn)$
  • while循环复杂度为$O(n)$
  • 总体复杂度是 $O(nlogn)$

class Solution:
    def twoSum(self, nums, target):
        temp = nums.copy()
        temp.sort()
        left = 0
        right = len(temp) - 1
        while left < right:
            small = temp[left]
            big = temp[right]
            if small + big == target:
                return [nums.index(small), nums.index(big)]
            elif small + big < target:
                left += 1
            else:
                right -= 1

3. 哈希表

• 遍历列表的每个数
• 每次遍历时，记录访问的差值diff（target - value）以及下标（index）
• 上述内容记录在哈希表中d = {diff: index}
• 每次遍历时进行判断，当某个值存在与d.keys()时，返回当前下标与d.values
  • dict的查找是时间复杂度是$O(1)$
  • 总体时间复杂度是$O(n)$

class Solution:
    def twoSum(self, nums, target):
        temp = dict()
        for i in range(len(nums)):
            if nums[i] in temp:
                return [temp.get(nums[i]), i]
            else:
                temp[target - nums[i]] = i