例题

1. 三数之和

image.png
思路

  • 双指针
  • 转化为两数之和

代码
Python代码：

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         nums.sort()
  4.         n = len(nums)
  5.         res = []
  6.         for i in range(n):
  7.             if i > 0 and nums[i-1] == nums[i]:
  8.                 continue
  10.             k = n - 1
  11.             target = -nums[i]
  12.             for j in range(i+1, n):
  13.                 if j > i+1 and nums[j] == nums[j-1]:
  14.                     continue
  16.                 while j < k and nums[j] + nums[k] > target:
  17.                     k -= 1
  19.                 if j == k:
  20.                     break
  21.                 if nums[j] + nums[k] == target:
  22.                     temp = [nums[i], nums[j], nums[k]]
  23.                     res.append(temp)
  24.         return res

Java代码：

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         Arrays.sort(nums);
  4.         int n = nums.length;
  5.         List<List<Integer>> res = new ArrayList<>();
  6.         for(int i = 0; i < n; i++) {
  7.             if (i > 0 && nums[i] == nums[i-1]) continue;
  8.             int k = n - 1;
  9.             int target = -nums[i];
  10.             for (int j = i + 1; j < n; j++) {
  11.                 if (j > i + 1 && nums[j] == nums[j-1]) continue;
  12.                 while(j < k && nums[j] + nums[k] > target) {
  13.                     k--;
  14.                 }
  15.                 if (j == k) break;
  16.                 if (nums[j] + nums[k] == target) {
  17.                     List<Integer> temp = new ArrayList<>();
  18.                     temp.add(nums[i]);
  19.                     temp.add(nums[j]);
  20.                     temp.add(nums[k]);
  21.                     res.add(temp);
  22.                 }
  23.             }
  24.         }
  25.         return res;
  26.     }
  27. }

JavaScript代码：

  1. var threeSum = function(nums) {
  2.     nums.sort((a, b) => {
  3.         if (a > b) {
  4.         return 1;
  5.         } 
  6.         if (a < b) {
  7.         return -1;
  8.         }
  9.         return 0;
  10.     });
  11.     let n = nums.length;
  12.     let res = [];
  13.     for (let i = 0; i < n; i++) {
  14.         if (i > 0 && nums[i] === nums[i-1]) continue;
  16.         let k = n - 1;
  17.         let target = -nums[i];
  18.         for (let j = i + 1; j < n; j++) {
  19.             if (j > i + 1 && nums[j] === nums[j-1]) continue;
  21.             while (j < k && nums[j] + nums[k] > target) {
  22.                 k--;
  23.             }
  25.             if (j === k) break;
  27.             if (nums[j] + nums[k] === target) {
  28.                 temp = [nums[i], nums[j], nums[k]]
  29.                 res.push(temp);
  30.             }
  31.         }
  32.     }
  33.     return res;
  34. };