两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

如果数组已经排序，那么可以使用双指针思想。

  1. class Solution:
  2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
  3.         nums.sort()
  4.         left, right = 0, len(nums) - 1
  5.         while left < right:
  6.             match = nums[left] + nums[right]
  7.             if match == target:
  8.                 return [left, right]
  9.             elif match > target:
  10.                 right -= 1
  11.             else:
  12.                 left += 1
  13.         return [-1, -1] #没有答案，返回[-1, -1]

没有排序，使用哈希表思想

  1. class Solution:
  2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
  3.         num_dict = {}
  4.         for idx, num in enumerate(nums):
  5.             if target - num not in num_dict:
  6.                 num_dict[num] = idx
  7.             else:
  8.                 return [idx, num_dict[target-num]]

三数之和

https://leetcode-cn.com/problems/3sum/
排序 + 三指针

  1. class Solution:
  2.     def threeSum(self, nums: [int]) -> [[int]]:
  3.         nums.sort()
  4.         res, k = [], 0
  5.         for k in range(len(nums) - 2):
  6.             if nums[k] > 0: break # 1. because of j > i > k.
  7.             if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
  8.             i, j = k + 1, len(nums) - 1
  9.             while i < j: # 3. double pointer
  10.                 s = nums[k] + nums[i] + nums[j]
  11.                 if s < 0:
  12.                     i += 1
  13.                     while i < j and nums[i] == nums[i - 1]: i += 1
  14.                 elif s > 0:
  15.                     j -= 1
  16.                     while i < j and nums[j] == nums[j + 1]: j -= 1
  17.                 else:
  18.                     res.append([nums[k], nums[i], nums[j]])
  19.                     i += 1
  20.                     j -= 1
  21.                     while i < j and nums[i] == nums[i - 1]: i += 1
  22.                     while i < j and nums[j] == nums[j + 1]: j -= 1
  23.         return res

四数之和

https://leetcode-cn.com/problems/4sum/