53. 最大子数组和
# 空间复杂度为1，时间复杂度为n
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_f = nums[0]
pre_f = nums[0]
for i in range(1, len(nums)):
pre_f = max(pre_f + nums[i], nums[i])
max_f = max(pre_f, max_f)
return max_f
152. 乘积最大子数组
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return
res = nums[0]
pre_max = nums[0]
pre_min = nums[0]
for num in nums[1:]:
cur_max = max(pre_max * num, pre_min * num, num)
cur_min = min(pre_max * num, pre_min * num, num)
res = max(res, cur_max)
pre_max = cur_max
pre_min = cur_min
return res
560. 和为 K 的子数组
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
# 要求的连续子数组
count = 0
n = len(nums)
preSums = dict()
preSums[0] = 1
presum = 0
for i in range(n):
presum += nums[i]
count += preSums.get(presum - k, 0)
preSums[presum] = preSums.get(presum, 0) + 1
return count
计算前缀和数组
int len = nums.length;
// 计算前缀和数组
int[] preSum = new int[len + 1];
preSum[0] = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
# 要求的连续子数组
count = 0
n = len(nums)
preSum = [0]
# 求前缀和数组
tmp = 0
for i in range(n):
tmp += nums[i]
preSum.append(tmp)
# 求和为k的连续子数组，求i到j之间的和
for i in range(1, n+1):
for j in range(i, n+1):
if preSum[j] - preSum[i-1] == k: # preSum[j] - preSum[i-1]代表着在nums数组中，前j个数之和减去前i-1个数之和
count += 1
return count
三数之和
def threeSum(nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
x = nums[i]
l = i + 1
r = n - 1
while l < r:
s = x + nums[l] + nums[r]
if s == 0:
ans.append([x, nums[l], nums[r]])
l += 1
# while l < r and nums[l] == nums[l - 1]:
# l += 1
r -= 1
# while l < r and nums[r] == nums[r + 1]:
# r -= 1
elif s > 0:
r -= 1
elif s < 0:
l += 1
return ans
11. 盛最多水的容器
def maxArea(height: List[int]) -> int:
ans = 0
left = 0
right = len(height) - 1
while left < right:
area = (right - left) * min(height[left], height[right])
ans = max(area, ans)
if height[right] > height[left]:
left += 1
else:
right -= 1
return ans
42. 接雨水
def trap(height: List[int]) -> int:
n = len(height)
ans = 0
pre_nums = [0] * n
suf_nums = [0] * n
pre_nums[0] = height[0]
suf_nums[-1] = height[-1]
for i in range(1, n):
pre_nums[i] = max(pre_nums[i - 1], height[i])
for i in range(n - 2, -1, -1):
suf_nums[i] = max(suf_nums[i + 1], height[i])
for i in range(n):
s = min(pre_nums[i], suf_nums[i]) - height[i]
ans += s
return ans
189. 轮转数组
[1, 2, 3, 4, 5, 6, 7] k = 3
[5, 6, 7, 1, 2, 3, 4]
def rotate_arr(nums: List[int], k: int) -> None:
n = len(nums)
new_arr = [0] * n
for i in range(n):
print((i + k) % n)
new_arr[(i + k) % n] = nums[i]
for i in range(n):
nums[i] = new_arr[i]
三次反转
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums)
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]
网友评论