两个指针

有效回文

时间复杂度: O(n)

空间复杂度: O(1)

def isPalindrome(s: str) -> bool:
  l, r = 0, len(s) - 1
  while l < r:
    while l < r and not s[l].isalnum():
      l += 1
    while l < r and not s[r].isalnum():
      r -= 1
    
    if s[l].lower() != s[r].lower():
      return False
    l += 1
    r -= 1
  return True

167 两个和 II - 输入数组已排序

时间复杂度: O(n)。 在最坏情况下，我们遍历每个数字并找到解决方案，即最后一对数字。

空间复杂度: O(1)。 唯一使用的额外空间是两个指针，这是一种常数。

def twoSum(numbers: List[int], target: int) -> List[int]:
  l, r = 0, len(numbers) - 1

  while l < r:
    res = numbers[l] + numbers[r]
  
    if res == target:
      return [l + 1, r + 1]
    elif res > target:
      r -= 1
    else:
      l += 1

15 三数和

设 nums 列表中的元素数量为 n。

时间复杂度

• 对输入数组进行排序需要 O(n log n)。
• 我们遍历数组一次，每次固定一个元素 (O(n))。
• 对于每个固定的元素，我们使用对剩余数组的部分进行两指针扫描 (O(n))。

综合来看：

• O(n log n + n²) = O(n²)

空间复杂度

• 数组在原位进行排序，并且仅使用少量指针，因此该算法需要 O(1) 的额外空间。
• 输出列表不计入辅助空间；在最坏情况下，它可能包含最多 O(n) 个三元组，其中 k 是有效解决方案的数量。

总辅助空间： O(1) (不包括输出)

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []

    for idx, i in enumerate(nums):
        if i > 0:
          break
        if idx > 0 and i == nums[idx - 1]:
          continue
        
        l, r = idx + 1, len(nums) - 1
        while l < r:
            total = i + nums[l] + nums[r]

            if total == 0:
                res.append([i, nums[l], nums[r]])
                l += 1
                r -= 1

                while l < r and nums[l] == nums[l - 1]:
                    l += 1
            elif total > 0:
                r -= 1
            else:
                l += 1
    return res

11 容纳最多雨水的容器

时间复杂度: O(n)。 我们遍历输入数组一次。

空间复杂度: O(1)。 唯一使用的额外空间是两个指针和结果，这两种都为常数。

def maxArea(height: List[int]) -> int:
  l, r = 0, len(height) - 1
  res = 0

  while l < r:
    res = max(res, min(height[l], height[r]) * (r - l))

    if height[l] >= height[r]:
      r -= 1
    else:
      l += 1
      
  return res

42 盛水

def trap(height: List[int]) -> int:
  res = 0
  prefix_max = []

  for h in height:
    if prefix_max:
      prefix_max.append(max(h, prefix_max[-1]))
    else:
      prefix_max.append(h)
  
  post_high = 0
  for i in range(len(height) - 1, 0, -1):
    post_high = max(post_high, height[i])
    res += min(prefix_max[i], post_high) - height[i]

  return res