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

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

# 题目 #

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

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

**示例**:

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

## 算法实现 ##

public static IList<IList<int>> ThreeSum(int[] nums)
    {
        
        IList<IList<int>> list = new List<IList<int>>();
        if (nums.Length == 0)
            return list;
        Array.Sort(nums);
        int length = nums.Length;
        int first, last, sum;
        if (nums[0] <= 0 && nums[length - 1] >= 0)
        {
        
            for (int i = 0; i < length - 2; )
            {
        
                if (nums[i] > 0) break;
                first = i + 1;
                last = length - 1;
                do
                {
        
                    if (first >= last || (double)nums[i] * nums[last] > 0 ) break;//注意乘法溢出
                    sum = nums[first] + nums[i] + nums[last];
                    if (sum == 0)
                        list.Add(new List<int>() {
         nums[i], nums[first], nums[last] });
                    if (sum <= 0 )
                    {
        
                        while (first < last && nums[first] == nums[++first]) ;
                    }
                    else
                    {
        
                        while (first < last && nums[last] == nums[--last]) ;
                    }
                } while (first < last);
                do
                {
        
                    if (i + 1 >= length - 2)
                        break;
                }
                while (nums[i] == nums[++i]);
                if (i + 1 >= length - 2)
                        break;
            }
        }
        return list;
    }

## 执行结果 ##

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

## 小的总结 ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/7908cc0ca6274032835b63840124ed91.png