LeetCode刷题（1）——持续更新中...
LeetCode刷题（1）
1、两数之和
给定一个整数数组 nums 和目标值 target，请你在该数组中找出和为目标值的两个整数，返回它们的数组下标。假设只有一组整数。
示例：
nums = [2,7,11,15], target = 9
#返回：
[0,1]
注意：题目容易出错的情况在于数组中出现两个相同的数字和 target - num = num 的情况。
1.1、暴力法
解题的关键是看 num2 = target - num1 是否在nums 中。因此需要两个方法：（1）成员资格检查；（2）nums.index(num2) 获取索引。
针对每一个方法需要注意的问题：
-
成员资格检查：
如果单纯地使用 num2 in nums，就可能遇到前面说的容易出错的那种情况，比如，nums = [3,2,1],target = 6，那么 num2 = 6-3 = 3 也在数组中，但是明显不符合题目要求。
-
nums.index(num2) 获取索引
从第一个方面可知，如果要从全局进行成员资格检查，则应该避免出现相同的索引。index() 函数返回的是列表中第一个与 obj 相等的元素的索引。比如：nums = [3,3],target = 6，nums = 3，如果使用 index() 函数则会找到索引为 0 的 3，也不是我们想要的。因此，我们应该在该元素之前或之后查找 num2。
#最简单的暴力法，双指针
def twoSum(nums,target):
lens = len(nums)
for i in range(lens):
for j in range(i+1,lens):
if(nums[i] + nums[j] == target):
return [i,j]
#但这种方法的运行时间太长，大约在 6068ms，内存占用：14.6MB
我们改使用一次 for 循环，在该元素之前查找 num2，以空间换时间：
def twoSum(nums,target):
lens = len(nums)
j = -1
for i in range(1,lens):
temp = nums[:i]
if (target - nums[i]) in temp:
j = temp.index(target - nums[i])
break
if j >= 0:
return [i,j]
#在元素之前查找也省去了截取列表再获取索引时索引相对位置的变化问题
#运行时间：468ms，内存大小：14.6MB
1.2、用字典来模拟哈希
只需要一次 for 循环，我们知道哈希查找数据是最快的。
def twoSum(nums,target):
hashmap = {}
for i,num in enumrate(nums):
if hashmap.get(target - num) is not None:
return [hashmap.get(target - num),i]
hashmap[num] = i #放在 if 语句之后，也是为了处理前面说的容易出错的情况
#运行时间：72ms，内存大小：15.1MB
2、删除排序数组中的重复元素
给定一个排序数组，你需要在 “原地” 删除重复的元素，返回移除后数组的新长度。
2.1、方法：双指针
数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 为慢指针，而 j 是快指针。只要 nums[i] = nums[j]，j 就往后移动，跳过重复项；
当 nums[i] ≠ nums[j] 时，跳过重复项已结束，因此我们必须把它（nums[j]）的值复制到 nums[i+1]。然后接着上面的过程继续，直到快指针到数组末尾。
def removeDuplicates(nums):
if len(nums) == 0:
return 0
i = 0
for j in range(1,len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i+1
#运行时间：52ms；内存大小：14.6MB
补充：此题目要求的是 “原地”，否则可以使用 set 集合，直接去掉重复元素，然后返回集合的个数即可。
3、移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
3.1、方法：双指针
题目还是要求 “原地” 修改（如果不是原地并且修改的话，可以使用列表中的 count() 方法，统计出 val 的个数，直接用列表长度减去 val 的个数即可）。
我们放置双指针 i 和 j，j 为快指针。跟上题的思路差不多，只是 if 的条件变成了 = val 而已。
def removeElement(nums: List[int], val: int) -> int:
if len(nums) == 0:
return 0
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
else:
continue
return i
#运行时间：44ms；内存大小：13.6MB