diff options
author | Jack Sangdahl <[email protected]> | 2025-09-25 21:03:37 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-25 21:03:37 -0600 |
commit | 23353c144ac9b158af7616dc46b636d53b73ce34 (patch) | |
tree | 3394d416aa99e9dc1c84cc07e663e6cc3d844570 | |
parent | afadd0bbf56f8aff8c5b397df08731c750302fd4 (diff) | |
download | leetcode-23353c144ac9b158af7616dc46b636d53b73ce34.tar.gz leetcode-23353c144ac9b158af7616dc46b636d53b73ce34.zip |
611. valid triangle number
-rw-r--r-- | valid_triangle_number.c | 31 | ||||
-rw-r--r-- | valid_triangle_number.py | 31 |
2 files changed, 62 insertions, 0 deletions
diff --git a/valid_triangle_number.c b/valid_triangle_number.c new file mode 100644 index 0000000..83585f7 --- /dev/null +++ b/valid_triangle_number.c @@ -0,0 +1,31 @@ +// 611. Valid Triangle Number +#include "leetcode.h" + +/* + * given an integer array 'nums', return the number of triplets chosen from the + * array that can make triangles if we take them as side lengths of a triangle + */ + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +int triangleNumber(int *nums, int numsSize) { + qsort(nums, numsSize, sizeof(int), cmp); + int ans = 0; + for (int k = 2; k < numsSize; ++k) { + int i = 0, j = k - 1; + while (i < j) { + if (nums[i] + nums[j] > nums[k]) { + ans += j - i; + j--; + } else + i++; + } + } + return ans; +} + +int main() { + int n1[] = {2, 2, 3, 4}, n2[] = {4, 2, 3, 4}; + printf("%d\n", triangleNumber(n1, ARRAY_SIZE(n1))); // expect: 3 + printf("%d\n", triangleNumber(n2, ARRAY_SIZE(n2))); // expect: 4 +} diff --git a/valid_triangle_number.py b/valid_triangle_number.py new file mode 100644 index 0000000..8460292 --- /dev/null +++ b/valid_triangle_number.py @@ -0,0 +1,31 @@ +# 611. Valid Triangle Number + +""" +given an integer array 'nums', return the number of triplets chosen from the +array that can make triangles if we take them as side lengths of a triangle +""" + + +class Solution(object): + def triangleNumber(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + nums.sort() + n, ans = len(nums), 0 + for k in range(2, n): + i, j = 0, k - 1 + while i < j: + if nums[i] + nums[j] > nums[k]: + ans += j - i + j -= 1 + else: + i += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.triangleNumber(nums=[2, 2, 3, 4])) + print(obj.triangleNumber(nums=[4, 2, 3, 4])) |