数组
两数之和
给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
思路：
看到这个题目要求返回符合要求的两个数的下标（索引），那就不可以排序了。首先想到的是两层排序，然后把符合要求的两个数的索引返回即可。代码如下：
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]
两层循环找到符合条件的两个数的索引，时间复杂度为O(n**2)，时间复杂度高会导致程序运行消耗太多时间，下面介绍另一种思路，来降低时间复杂度。
可以将所有的数存到一个字典里面（哈希表）。字典的key是nums中的数字，value为nums[key]。这样只需要再遍历的时候查看target - nums[i]是否在字典中即可。时间复杂度为O(n)。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
if target - nums[i] in dic:
return [i, dic[target - nums[i]]]
else:
dic[nums[i]] = i
最接近的三数之和
给你一个长度为 n的整数数组 nums和 一个目标值 target。请你从 nums中选出三个整数，使它们的和与 target最接近。返回这三个数的和。假定每组输入只存在恰好一个解。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
输入：nums = [0,0,0], target = 1
输出：0
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
通过次数303,330提交次数660,9
思路：
最简单的思路当然就是三层遍历，但是如此时间复杂度会很大，代码如下：
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
res = float('inf')
sum = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
for k in range(j+1, len(nums)):
if abs(nums[i] + nums[j] + nums[k] - target) < res:
res = min(res, abs(nums[i] + nums[j] + nums[k] - target))
sum = abs(nums[i] + nums[j] + nums[k])
return sum
其外，可以对数组先排序，然后双指针找到最接近的三个数，具体代码实现如下：
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort() # 排序
res = nums[0] + nums[1] + nums[2] # 赋予res一个初始值
for i in range(len(nums)-2): # 进入循环
start, end = i + 1, len(nums) - 1 # 设置指针
while start < end:
sum = nums[start] + nums[i] + nums[end]
if abs(target - sum) < abs(target - res):
res = sum
if sum > target:
end -= 1
elif sum < target:
start += 1
else:
return res
return res
排序的时间复杂度为O(nlogn)，后面双指针嵌套两层循环时间复杂度为O(n**2)。所以代码的时间复杂为O(n**2)。
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
输入：nums = []
输出：[]
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
思路：
此题与最接近的三数之和思路和代码大体相同，但这道题的难点在于去重。代码时间复杂度仍为O(n**2)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums) - 2):
# 确保所有相同的num[i]，只从最后一个num[i]开始循环
if i > 0 and nums[i] == nums[i - 1]:
continue # 跳出遇到当前数与下一个数相同情况，就跳过跳过此数直接去下一个数。
start, end = i + 1, len(nums) - 1 # 设置指针
while start < end:
tmp = nums[i] + nums[start] + nums[end]
if tmp == 0:
res.append([nums[i], nums[start], nums[end]])
# 去重与上面的操作类似，如果当前数与下一个数相同就直接去下一个数。不同的是这里不需要跳出循环
while start != end and nums[start] == nums[start + 1]: start += 1
while start != end and nums[end] == nums[end - 1]: end -= 1
start += 1
end -= 1
elif tmp < 0:
start += 1
else:
end -= 1
return res
删除有序数组中的重复项
给你一个 升序排列 的数组 nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums的前 k 个元素应该保存最终结果。将最终结果插入 nums的前 k 个位置后返回 k 。不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
思路：
这道题要跳出逻辑陷阱，直接就把这个数组当成一个空数组，从前往后遍历，只把不同的数放进去。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow=0
for quick in range(1,len(nums)):
if nums[slow]!=nums[quick]:
slow=slow+1
nums[slow]=nums[quick]
return slow+1
移除元素
给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于 val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
思路：
与删除有序数组中的重复项一样，直接就把nums当成一个空数组，有不等于val的数，就覆盖掉之前的数。快慢指针。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
for quick in range(len(nums)):
if nums[quick] != val:
nums[slow] = nums[quick]
slow += 1
return slow
搜索旋转排序数组
整数数组 nums按升序排列，数组中的值 互不相同 。在传递给函数之前，nums在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums和一个整数 target ，如果 nums中存在这个目标值 target，则返回它的下标，否则返回 -1 。
示例：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
思路：
一种就是直接遍历寻找，代码如下：
class Solution:
def search(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
但是这样的话就浪费了nums旋转前的排序状态，所以可以用二分查找的变体来解题，代码如下：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[len(nums) - 1]:
left = mid + 1
else:
right = mid - 1
return -1
