【第十一天 - Two-pointer 题目分析】

先简单回顾一下，今天预计分析两个题目：

• 26. Remove Duplicates from Sorted Array
• 167. Two Sum II - Input array is sorted

26. Remove Duplicates from Sorted Array

• 题目连结：https://leetcode.com/problems/valid-parentheses/

• 题目叙述：

  • 题目会给你一个从小排序到大的资料，但是里面有重复的元素，你需要把他删掉
  • 有些语言是不能把资料里的元素删掉 ( array 长度不能被改变)，所以你需要把後面所有元素往前平移
  • 不过我们这边使用的是 python，可以删除任意位置的元素 ，所以只要遇到多余的就删掉即可

  

• 测资的 Input/Output

  • 题目如果给你 [1,1,2] 那你要把多余的元素删掉，并回传不重复元素个数

    

• python 实作如下：

  • 根据题目要求，不能使用额外的空间，那麽就使用 Two-pointer 的概念，
    • nums 把不重复的资料往前填
      1. 初始状态，我们将 k 跟 j 从第2个数字开始看，因为第一个数字一定不重复，所以直接从第二个看
         1. j 会从第2个数字开始走访每一个位置，一次一格，直到指到尾
         2. k 会先停在第2个数字，当 j 找到不一样的元素，那 nums[k] 会储存 nums[j]，然後 k 再往後一格，等待 j 再次找到不同的元素
      2. 随着 j 的走访，每次会比较第 j 个跟第 j-1 个数字是否一致
         1. 若不一致，代表第 j 个值不是重复元素，就可以安心把 第 k 个储存 第 j 个的值，并且 k 再往右移动一格 ( 在尚未遇到重复元素时，j 跟 k 都会指向同一个地方)
         2. 若一致，代表第 j 个是重复元素，那就不做任何事，直到 j 指向非重复元素，那麽第 k 个位置( k 停在遇到的第一个重复元素的位置)，就会储存第 j 个的值( j 停在非重复元素的位置)

  

- python 实作

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
#       k 会用来计算不重复元素的位置
        k = 1
#       j 会走得比较快，把不重复的值，丢给 k 位置储存
        for j in range(1, len(nums)):
#           判断第 j 个位置跟第 j-1 的位置，是否不相等，若不相等，就把 nums[k] 储存 nums[j]，并 k 向右移动
            if nums[j] != nums[j - 1]:
                nums[k] = nums[j]
                k += 1

        return k

• 非 Two-pointer 解法
  • python nums 把资料 pop 出来
    • 每次遇到重复的值，就将他删掉，不过删掉後，後面的资料会直接递补删掉的位置，所以要进行 j -=1，免得比对的时候跳过新递补的数字

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        while j < len(nums):
            if nums[j] == nums[j-1]:
                nums.pop(j)  
                j -= 1
            j += 1
        return len(nums)

• python 使用内建的 function
  • set 会自动把多余的元素删除
  • 接着再用 sort 重新排列
  • nums[:] 则是可以把 nums 全部的资料改成储存刚刚删除并排列好的

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums[:] = sorted(set(nums))
        return len(nums)

167. Two Sum II - Input array is sorted

• 题目连结：https://leetcode.com/problems/valid-parentheses/

• 题目叙述：

  • 题目会给你一个从小排序到大的资料，跟希望找到的两数相加的和 (target)

  • 你需要找出哪两个位置的值，相加会等於 target

  • 哪两个位置的值相加为 target，只会有一种答案

  • 同一个元素不能加两次

    

• 测资的 Input/Output

  • 题目会给你一个递增的数列，跟希望找到的目标总和 (target)

  • 回传一个 list 结构的资料，里面要包含相加会等於 target 的 index

    

• python 实作

  

  

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers)-1

        while not numbers[left] + numbers[right] == target:
            while numbers[left] + numbers[right] > target and left != right:
                right -= 1 
            while numbers[left] + numbers[right] < target and left != right:
                left += 1

        return [left+1,right+1]