剑指offer刷题笔记--Num51-60

**剑指Offer刷题笔记--Num51-60**

### Num51. 数组中的逆序对**问题描述:**
给定一个长度为n的数组，求出其中所有数字两两相加的逆序对的数量。

**示例:**
输入:[1,2,3,4,5]
输出:16**解决方案:**

def reversePairs(nums):
 def mergeSort(left, right):
 if left == right:
 return0 mid = (left + right) //2 count = mergeSort(left, mid) + mergeSort(mid +1, right)
 # 将左半部分和右半部分合并到一起 i, j = left, mid +1 temp = []
 while i <= mid and j <= right:
 if nums[i] > nums[j]:
 count += mid - i +1 temp.append(nums[j])
 j +=1 else:
 temp.append(nums[i])
 i +=1 # 将剩余的元素添加到temp中 while i <= mid:
 temp.append(nums[i])
 i +=1 while j <= right:
 temp.append(nums[j])
 j +=1 nums[left:right +1] = temp return count return mergeSort(0, len(nums) -1)

### Num52. 最大子序列和**问题描述:**
给定一个长度为n的数组，求出其中最大连续子序列的和。

**示例:**
输入:[-2,1,-3,4,-1,2,1,-5,4]
输出:6**解决方案:**

def maxSubArray(nums):
 if not nums:
 return0 dp = [0] * len(nums)
 dp[0] = nums[0]
 for i in range(1, len(nums)):
 dp[i] = max(dp[i -1], nums[i])
 return max(dp)

### Num53. 最大子序列乘积**问题描述:**
给定一个长度为n的数组，求出其中最大连续子序列的乘积。

**示例:**
输入:[2,3,-2,4]
输出:6**解决方案:**

def maxProduct(nums):
 if not nums:
 return0 dp = [0] * len(nums)
 dp[0] = nums[0]
 for i in range(1, len(nums)):
 dp[i] = max(dp[i -1], nums[i])
 min_val = max_val = nums[0]
 for num in nums:
 if num < 0:
 min_val, max_val = max_val, min_val min_val = min(min_val, num)
 max_val = max(max_val, num)
 return max_val

### Num54. 最大子序列和为k的子序列**问题描述:**
给定一个长度为n的数组和一个整数k，求出其中最大连续子序列的和等于k。

**示例:**
输入:[1,2,-2,3], k =3输出:3**解决方案:**

def maxSubArrayLen(nums, k):
 if not nums or k < 0:
 return0 prefix_sum = [0] * (len(nums) +1)
 for i in range(len(nums)):
 prefix_sum[i +1] = prefix_sum[i] + nums[i]
 max_len =0 for i in range(len(nums) +1):
 for j in range(i, len(nums) +1):
 if prefix_sum[j] - prefix_sum[i -1] == k:
 max_len = max(max_len, j - i)
 return max_len

### Num55. 最大子序列和为k的子序列（二分查找）

**问题描述:**
给定一个长度为n的数组和一个整数k，求出其中最大连续子序列的和等于k。

**示例:**
输入:[1,2,-2,3], k =3输出:3**解决方案:**

def maxSubArrayLen(nums, k):
 if not nums or k < 0:
 return0 prefix_sum = [0] * len(nums)
 for i in range(len(nums)):
 prefix_sum[i] = prefix_sum[i -1] + nums[i]
 left, right =0, len(nums) -1 while left <= right:
 mid = (left + right) //2 if prefix_sum[mid] == k:
 return mid +1 elif prefix_sum[mid] < k:
 left = mid +1 else:
 right = mid -1 return -1

### Num56. 最大子序列和为k的子序列（前缀和）

**问题描述:**
给定一个长度为n的数组和一个整数k，求出其中最大连续子序列的和等于k。

**示例:**
输入:[1,2,-2,3], k =3输出:3**解决方案:**

def maxSubArrayLen(nums, k):
 if not nums or k < 0:
 return0 prefix_sum = [0] * len(nums)
 for i in range(len(nums)):
 prefix_sum[i] = prefix_sum[i -1] + nums[i]
 max_len =0 for i in range(len(nums) +1):
 for j in range(i, len(nums) +1):
 if prefix_sum[j] - prefix_sum[i -1] == k:
 max_len = max(max_len, j - i)
 return max_len

### Num57. 和为k的子序列**问题描述:**
给定一个长度为n的数组和一个整数k，求出其中所有数字之和等于k的子序列。

**示例:**
输入:[1,2,-2,3], k =3输出:[[1,2],[3]]

**解决方案:**

def subarraySum(nums, k):
 if not nums:
 return []
 prefix_sum = [0] * len(nums)
 for i in range(len(nums)):
 prefix_sum[i] = prefix_sum[i -1] + nums[i]
 res = []
 for i in range(len(nums) +1):
 for j in range(i, len(nums) +1):
 if prefix_sum[j] - prefix_sum[i -1] == k:
 res.append(nums[i -1:j])
 return res

### Num58. 和为k的子序列（前缀和）

**问题描述:**
给定一个长度为n的数组和一个整数k，求出其中所有数字之和等于k的子序列。

**示例:**
输入:[1,2,-2,3], k =3输出:[[1,2],[3]]

**解决方案:**

def subarraySum(nums, k):
 if not nums:
 return []
 prefix_sum = [0] * len(nums)
 for i in range(len(nums)):
 prefix_sum[i] = prefix_sum[i -1] + nums[i]
 res = []
 for i in range(len(nums) +1):
 for j in range(i, len(nums) +1):
 if prefix_sum[j] - prefix_sum[i -1] == k:
 res.append(nums[i -1:j])
 return res

### Num59. 和为k的子序列（二分查找）

**问题描述:**
给定一个长度为n的数组和一个整数k，求出其中所有数字之和等于k的子序列。

**示例:**
输入:[1,2,-2,3], k =3输出:[[1,2],[3]]

**解决方案:**

def subarraySum(nums, k):
 if not nums:
 return []
 prefix_sum = [0] * len(nums)
 for i in range(len(nums)):
 prefix_sum[i] = prefix_sum[i -1] + nums[i]
 res = []
 left, right =0, len(nums) -1 while left <= right:
 mid = (left + right) //2 if prefix_sum[mid] == k:
 res.append(nums[:mid +1])
 break elif prefix_sum[mid] < k:
 left = mid +1 else:
 right = mid -1 return res

### Num60. 和为k的子序列（前缀和）

**问题描述:**
给定一个长度为n的数组和一个整数k，求