LeetCode题目之腾讯精选练习（50题）：三数之和

墨蓝 2024-04-17 20:43 163阅读 0赞

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例:

  1. 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  3. 满足要求的三元组集合为：
  4. [
  5.   [-1, 0, 1],
  6.   [-1, -1, 2]
  7. ]

算法实现

  1. public static IList<IList<int>> ThreeSum(int[] nums)
  2. {
  4.     IList<IList<int>> list = new List<IList<int>>();
  5.     if (nums.Length == 0)
  6.         return list;
  7.     Array.Sort(nums);
  8.     int length = nums.Length;
  9.     int first, last, sum;
  10.     if (nums[0] <= 0 && nums[length - 1] >= 0)
  11.     {
  13.         for (int i = 0; i < length - 2; )
  14.         {
  16.             if (nums[i] > 0) break;
  17.             first = i + 1;
  18.             last = length - 1;
  19.             do
  20.             {
  22.                 if (first >= last || (double)nums[i] * nums[last] > 0 ) break;//注意乘法溢出
  23.                 sum = nums[first] + nums[i] + nums[last];
  24.                 if (sum == 0)
  25.                     list.Add(new List<int>() {
  26.      nums[i], nums[first], nums[last] });
  27.                 if (sum <= 0 )
  28.                 {
  30.                     while (first < last && nums[first] == nums[++first]) ;
  31.                 }
  32.                 else
  33.                 {
  35.                     while (first < last && nums[last] == nums[--last]) ;
  36.                 }
  37.             } while (first < last);
  38.             do
  39.             {
  41.                 if (i + 1 >= length - 2)
  42.                     break;
  43.             }
  44.             while (nums[i] == nums[++i]);
  45.             if (i + 1 >= length - 2)
  46.                     break;
  47.         }
  48.     }
  49.     return list;
  50. }

执行结果

执行结果 : 通过
执行用时 : 472 ms, 在所有 C# 提交中击败了78.01%的用户
内存消耗 : 34.3 MB, 在所有 C# 提交中击败了32.10%的用户
在这里插入图片描述

小的总结

本次题目较难，自己设计算法时没有解答出来，后来借鉴了题解的第一个——双指针，在移植到c#过程中发现一些bug：
1、三人同符号的判断存在乘法溢出问题
2、++i问题存在数组越界问题
之后经行了一些改进，成功完成了。

发表评论

表情：
评论列表 （有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读