categories: [Blog,Algorithm]

15. 三数之和

难度中等3030
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

  1.     public List<List<Integer>> threeSum(int[] nums) {
  2.         int n = nums.length;
  3.         Arrays.sort(nums);
  4.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
  5.         // 枚举 a
  6.         for (int first = 0; first < n; ++first) {
  7.             // 需要和上一次枚举的数不相同
  8.             if (first > 0 && nums[first] == nums[first - 1]) {
  9.                 continue;
  10.             }
  11.             // c 对应的指针初始指向数组的最右端
  12.             int third = n - 1;
  13.             int target = -nums[first];
  14.             // 枚举 b
  15.             for (int second = first + 1; second < n; ++second) {
  16.                 // 需要和上一次枚举的数不相同
  17.                 if (second > first + 1 && nums[second] == nums[second - 1]) {
  18.                     continue;
  19.                 }
  20.                 // 需要保证 b 的指针在 c 的指针的左侧
  21.                 while (second < third && nums[second] + nums[third] > target) {
  22.                     --third;
  23.                 }
  24.                 // 如果指针重合，随着 b 后续的增加
  25.                 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
  26.                 if (second == third) {
  27.                     break;
  28.                 }
  29.                 if (nums[second] + nums[third] == target) {
  30.                     List<Integer> list = new ArrayList<Integer>();
  31.                     list.add(nums[first]);
  32.                     list.add(nums[second]);
  33.                     list.add(nums[third]);
  34.                     ans.add(list);
  35.                 }
  36.             }
  37.         }
  38.         return ans;
  39.     }
  41. 作者：LeetCode-Solution
  42. 链接：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/

没太懂边界问题

  1.     ///至少一个正数一个负数 
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         int n = nums.length;
  4.         Arrays.sort(nums);
  5.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
  6.         // 枚举 a
  7.         for (int first = 0; first < n; ++first) {
  8.             // 需要和上一次枚举的数不相同
  9.             if (first > 0 && nums[first] == nums[first - 1]) {
  10.                 continue;
  11.             }
  12.             // c 对应的指针初始指向数组的最右端
  13.             int third = n - 1;
  14.             int target = -nums[first];
  15.             // 枚举 b
  16.             for (int second = first + 1; second < n; ++second) {
  17.                 // 需要和上一次枚举的数不相同
  18.                 if (second > first + 1 && nums[second] == nums[second - 1]) {/// >=
  19.                     continue;
  20.                 }
  21.                 // 需要保证 b 的指针在 c 的指针的左侧
  22.                 while (second < third && nums[second] + nums[third] > target) {/// <=
  23.                     --third;
  24.                 }
  25.                 // 如果指针重合，随着 b 后续的增加
  26.                 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
  27.                 if (second == third) { /// > 
  28.                     break;
  29.                 }
  30.                 if (nums[second] + nums[third] == target) {
  31.                     List<Integer> list = new ArrayList<Integer>();
  32.                     list.add(nums[first]);
  33.                     list.add(nums[second]);
  34.                     list.add(nums[third]);
  35.                     ans.add(list);
  36.                 }
  37.             }
  38.         }
  39.         return ans;
  40.     }