leetcode 167& 209

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