对撞指针

167. 两数之和 II - 输入有序数组

  1. # 时间复杂度为O(n); 空间复杂度为O(1)
  2. class Solution:
  3.     def twoSum(self, numbers, target):
  4.         i, j = 0, len(numbers)-1
  5.         while i < j:
  6.             if numbers[i] + numbers[j] == target:
  7.                 break
  8.             elif numbers[i] + numbers[j] < target:
  9.                 i += 1
  10.             else:
  11.                 j -= 1
  12.         return [i+1, j+1]

快慢指针

142. 环形链表 II

  1. class Solution:
  2.     def detectCycle(self, head):
  3.         fast, slow = head, head
  4.         while fast != None:
  5.             fast = fast.next
  6.             if fast == None:
  7.                 break
  8.             fast = fast.next
  9.             slow = slow.next
  10.             if fast == slow:
  11.                 break
  12.         if fast == None:
  13.             return None
  14.         p1, p2 = slow, head
  15.         while p1 != p2:
  16.             p1 = p1.next
  17.             p2 = p2.next
  18.         return p1