专栏首页大白技术控的技术自留地C#版 - Leetcode611.有效三角形的个数 - 题解

C#版 - Leetcode611.有效三角形的个数 - 题解

C#版 - Leetcode611. Valid Triangle Number - 题解

Leetcode 611. 有效三角形的个数

在线提交: https://leetcode-cn.com/problems/valid-triangle-number/

题目描述

给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]
输出: 3

解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  1. 数组长度不超过1000。
  2. 数组里整数的范围为 [0, 1000]。

  • 题目难度:Medium
  • 通过次数:266
  • 提交次数:691
  • 贡献者:LeetCode
  • 相关话题 数组 相似题目 3Sum Smaller

思路:

题中的要求数组长度不超过1000,事实上限制了算法的时间复杂度要小于O(n3)O(n3)O(n^3)。 先排序,然后采用贪心法的思想,算法复杂度可降低至O(n2)O(n2)O(n^2),如下图所示:

伪代码:

sort(nums)

for c = n-1 to 2 
  a, b = 0, c-1
  while a<b: 
    if nums[a] + nums[b] > nums[c]: 
        count += (a-b+1)-1
        b--
    else 
        a++

已AC代码:

public class Solution
{
    public int TriangleNumber(int[] nums)  
    {
        var n = nums.Length;
        if (n < 3)
            return 0;

        Array.Sort(nums);
        // Array.Sort(array, (x, y) => -x.CompareTo(y));
        var groupCount = 0;

        for (int c = n - 1; c >= 2; c--)
        {
            int b = c - 1;
            int a = 0;
            while (a != b)
            {
                if (nums[a] + nums[b] > nums[c])
                {
                    groupCount += b - a; // 贪心法,只要此时满足不等式,则仅有a在该区间内移动(b,c不变)时,显然也满足不等式
                    b--;
                }
                else
                    a++;
            }
        }

        return groupCount;
    }
}

Rank:

You are here! Your runtime beats 93.15% of csharp submissions.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#版 - LeetCode1 - TwoSum - 题解

    提交网址: https://leetcode.com/problems/two-sum/

    Enjoy233
  • C++版 - Leetcode 15. 3Sum 题解

    在线提交网址: https://leetcode.com/problems/3sum/

    Enjoy233
  • C++版 - Leetcode No.1 - Two sum题解

    提交网址: https://leetcode.com/problems/two-sum/

    Enjoy233
  • LeetCode92|排序数组

    当我们对其API比较熟悉时,合理使用已有的api对解题速度还是比较合理的,但是不可依赖它,毕竟不重复造轮子也不太好

    码农王同学
  • 关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

    关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3 方法2 方法2:遍历数组,遇到...

    WZEARW
  • 101. 删除排序数组中的重复数字 II

    允许出现两次重复的意思就是说两次重复不算重复,和一次重复的略有不同,只需要一个计数器来计算是否有两次重复就可以了。

    和蔼的zhxing
  • LeetCode 283:移动零 Move Zeroes

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    爱写bug
  • 算法-删除已排序数组中的重复项

    版权声明: h...

    Fisherman渔夫
  • LeetCode 283:移动零 Move Zeroes

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    爱写bug
  • LeetCode 每日一题 1480. 一维数组的动态和

    “给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。

    村雨遥

扫码关注云+社区

领取腾讯云代金券