leetcode 167& 209
【摘要】
167: 给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
...
167:
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
# 暴力解法
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
return i+1, j+1
return -1
# 数组升序,如[2, 7, 11, 15],target = 9,依次遍历每个数,如第一次为2, 在剩下数中用二分查找法寻找target - 2.依次类推
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
def binary_search(left, right, minus_target):
while left <= right:
mid = left + (right - left) // 2
if numbers[mid] == minus_target:
return mid + 1
elif numbers[mid] < minus_target:
left = mid + 1
else:
right = mid - 1
return False # 这里false也可以不写,如果没找到返回None,在下面判断中依旧不能进入if条件句。
for i in range(len(numbers) - 1): # i遍历所有的数,如果存在解,也是第一个数对应的索引
minus_target = target - numbers[i]
left = i + 1
second_index = 0
right = len(numbers) - 1
second_index = binary_search(left, right, minus_target)
if second_index:
break
return i + 1, second_index
# 对撞指针
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
left = 0 # 左边指针
right = len(numbers) - 1 # 右边指针
#判断左边指针与右边指针对应数的和,如果小于,说明左边指针右走会接近target(数组有序),其他情况类似
while left < right:
two_nums_sum = numbers[left] + numbers[right]
if two_nums_sum == target:
return left + 1, right + 1
elif two_nums_sum < target:
left += 1
else:
right -= 1
209:
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
# 滑动窗口:两个指针left和right,一旦left和right中间数的和小于s, 那么right右移(增加数)反之,left右移(减少数)
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
left = 0
right = -1 # 滑动窗口初始化没有数,且范围是[left, right]左闭右闭,故right初始化为-1
sum_length = len(nums) + 1 # 求和那些数的长度,初始化一个最大的(其实不可能达到),一旦碰到比他小的,重新赋值为更小的
my_sum = 0 # 滑动窗口初始化没有数,故sum初始化为0
while left < len(nums): # 一旦left无法右移,就可以终止条件了(即达到最后一个数了)
if my_sum < s and right + 1 < len(nums): # right + 1判断是因为满足条件后right先加1,sum再加上right,如果本来right就是最后一个,再加1,下面索引就会报错
right += 1
my_sum += nums[right]
else:
my_sum -= nums[left]
left += 1
if (my_sum >= s):
sum_length = min(sum_length, right - left + 1) # 本次过程一旦sum大于s,就可以判断初始化长度和现在长度哪个小,重新赋值
if sum_length == len(nums) + 1:
return 0
return sum_length
# 对上面方法的改进:在循环中,如果遇到right已经跑到最后一个,但是sum却还没有大于s,且left还没达到最后一个,这时候就可以终止循环了;
# 因为此时就会执行else语句,left+1,本来就小于s,left再+1,和更小。因此先判断sum<s,满足时,再判断right是否为最后一个;
# 如果是就可以终止循环了,如果不是,就按照上面思想继续运行。
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
left = 0
right = -1
sum_length = len(nums) + 1
my_sum = 0
while left < len(nums):
if my_sum < s:
if right + 1 < len(nums):
right += 1
my_sum += nums[right]
else:
break
else:
my_sum -= nums[left]
left += 1
if (my_sum >= s):
sum_length = min(sum_length, right - left + 1)
if sum_length == len(nums) + 1:
return 0
return sum_length
文章来源: blog.csdn.net,作者:weixin_43178406,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/weixin_43178406/article/details/86683372
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)