day6: 数组

1.  18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为： [   [-1,  0, 0, 1],   [-2, -1, 1, 2],   [-2,  0, 0, 2] ]

解法1:   做的想哭！超时！超时！超时    排序+双指针

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: # 四数之和， 首先排序， 前两次遍历， 后两次查询 nums.sort() nums_len = len(nums) temp = [] result = [] for i in range(nums_len-3): for j in range(i+1, nums_len-2): two = nums[i] + nums[j] p = j + 1 q = nums_len - 1 while p < q: # 遍历 if two + nums[p] + nums[q] == target: a = [nums[i], nums[j], nums[p], nums[q]] if set(a) not in temp: temp.append(set(a)) result.append(a) # 注意此处 不是elif， 所以相等时 可以跳出循环； if two + nums[p] + nums[q] > target: q -= 1 # 大于target 大的减小 else: p += 1 return result

解法2: 排序+双指针， 注意和解法1的 区别， 判别条件

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: # 四数之和， 首先排序， 前两次遍历， 后两次查询 nums.sort() nums_len = len(nums) temp = [] result = [] for i in range(nums_len-3): for j in range(i+1, nums_len-2): two = nums[i] + nums[j] p = j + 1 q = nums_len - 1 while p < q: # 遍历 if two + nums[p] + nums[q] == target: # 不会陷入死循环吗？ a = [nums[i], nums[j], nums[p], nums[q]] if set(a) not in temp: temp.append(set(a)) result.append(a) # 设置相等后 调整p, q if p < q and nums[p]==nums[p+1]: p = p + 1 if p < q and nums[q-1]==nums[q]: q = q - 1 p = p + 1 q = q - 1 elif two + nums[p] + nums[q] > target: q -= 1 # 大于target 大的减小 else: p += 1 return result

2. 15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

解法1:   7076 ms  排序+双指针

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # 排序 nums_len = len(nums) nums.sort() target = 0 # 遍历 temp = [] sets = [] for i in range(0, nums_len-2): # 三数 第一个数 遍历； 四数之和 前两个数都遍历； 其余利用有序特性； p = i + 1 q = nums_len - 1 while p < q: if nums[i]+nums[p]+nums[q] == target: a = [nums[i], nums[p], nums[q]] if set(a) not in sets: sets.append(set(a)) temp.append(a) # 这部分加， 不加可能漏掉， 没加 也通过了测试 😷 while p < q and nums[p]==nums[p+1]: p += 1 while p < q and nums[q-1] == nums[q]: q -= 1 p = p + 1 # 大的减小，小的增大 还有可能相等； q = q - 1 elif nums[i]+nums[p]+nums[q] > target: q = q - 1 else: p = p + 1 return temp

3. 189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的 原地 算法。

方法1:

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ nums_len = len(nums) k = k % nums_len temp = nums[-k:] # O(n)空间 不太符合 空间 要求； for i in range(nums_len-1, -1, -1): nums[i] = nums[i-k] for i in range(len(temp)): nums[i] = temp[i] return nums

解法2:  三次反转， 1:先反转数组； 2:再反转前k个数，3:再反转后n-k个数

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ nums_len = len(nums) k = k % nums_len # 三次反转， 1:先反转数组； 2:再反转前k个数，3:再反转后n-k个数 # nums = nums[::-1] # # print(nums) # nums[:k] = nums[:k][::-1] # # print(nums) # nums[k:] = nums[k:][::-1] # 没有改变值 def reverse(nums, start, end): while start < end: temp = nums[start] nums[start] = nums[end] nums[end] = temp start += 1 end -= 1 reverse(nums, 0, nums_len-1) reverse(nums, 0, k-1) reverse(nums, k, nums_len-1) # O(n), O(1)

4. 48. 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]

解法1: 顺时针 旋转90 = 水平翻转 + 主对角线翻转， 有点取巧

class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ # 水平反转 + 主对角线反转 = 顺时针旋转90度， 不遇见过，很难做出来 # 水平反转 row_len = len(matrix) col_len = len(matrix[0]) i = 0 j = row_len - 1 while i < j: # 水平反转操作 for index in range(col_len): matrix[i][index], matrix[j][index] = matrix[j][index], matrix[i][index] i = i + 1 j = j -1 # 主对角线旋转 for i in range(row_len): for j in range(i): # 不超过i 就行 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]