双指针应用一:碰撞指针

1、翻转数组中的元素:s = ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']

算法思路:定义左指针 i=0, 右指针 r = len(s)-1。交换指针对应的元素,然后同时向中间移动指针,直到指针碰撞。在指针移动的同时,交换指针指代的元素。

def reverseStr(s):
    l=0
    r=len(s)-1
    while l<r:
        s[l],s[r]=s[r],s[l]
        l+=1
        r-=1
    return s

s = ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']
print(reverseStr(s))

2、两数之和:给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

      示列:输入:numbers = [2, 7, 11, 15], target = 9   输出:[1 2].  解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

     算法思路:定义左指针 l=0, 右指针 r=len(nums)-1 。计算两个指针指代的元素之和:sum=nums[l]+nums[r]。如果sum<target,向中间移动左指针;如果sum>target,

   右指针向左边移动。直到sum==target,返回 [l+1,r+1]。

def twoSum(nums,target):
    l=0
    r=len(nums)-1
    while l<r:
        sum=nums[l]+nums[r]
        if sum>target:
            r-=1
        elif sum<target:
            l+=1
        else:
            return (l+1,r+1)
            
        
nums=[2, 7, 11, 15]
target=9
print(twoSum(nums,target))

 


 

上一篇:python 两数之和 II - 输入有序数组


下一篇:1879. 两数之和 VII