{"id":2565,"date":"2018-05-08T22:16:00","date_gmt":"2018-05-08T14:16:00","guid":{"rendered":"https:\/\/boweihe.me\/?p=2565"},"modified":"2018-05-08T22:16:00","modified_gmt":"2018-05-08T14:16:00","slug":"leetcode-611-valid-triangle-number","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2565","title":{"rendered":"LeetCode 611. Valid Triangle Number"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/valid-triangle-number\/description\/<br \/>\n\u6709\u70b9\u7c7b\u4f3c3Sum\u7684\u9898\u76ee\u3002\u5f62\u6210\u4e09\u89d2\u5f62\u7684\u5145\u8981\u6761\u4ef6\u662f\u6700\u5c0f\u4e24\u8fb9\u4e4b\u548c\u5927\u4e8e\u7b2c\u4e09\u8fb9\u3002\u53ef\u4ee5\u5148\u7ed9\u6570\u7ec4\u6392\u5e8f\uff0c\u7136\u540e\u786e\u5b9a\u4e00\u4e2a\u6700\u5927\u8fb9\uff0c\u7136\u540e\u5728\u5b83\u5de6\u8fb9\u627e\u53e6\u5916\u4e24\u8fb9\u3002<br \/>\n\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n*log(n) + n^2) = O(n^2)<\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    int triangleNumber(vector&lt;int&gt;&amp; nums) {\n        sort(nums.begin(), nums.end());\n        int count = 0;\n        for (int i = nums.size() - 1; i &gt;= 0; --i)\n        {\n            \/\/ two sum (x + y) &gt; nums[i]\n            int j = 0;\n            int k = i - 1;\n            while (j &lt; k)\n            {\n                if (nums[j] + nums[k] &lt;= nums[i])\n                {\n                    j++;\n                    continue;\n                }\n                count += (k - j);\n                k--;\n            }\n        }\n        return count;\n    }\n};<\/pre>\n<p>&nbsp;<br \/>\n&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/valid-triangle-number\/description\/ \u6709\u70b9\u7c7b\u4f3c3Sum\u7684\u9898\u76ee\u3002\u5f62\u6210\u4e09\u89d2\u5f62\u7684\u5145\u8981\u6761\u4ef6\u662f\u6700\u5c0f\u4e24\u8fb9\u4e4b\u548c\u5927\u4e8e\u7b2c\u4e09\u8fb9\u3002\u53ef\u4ee5\u5148\u7ed9\u6570\u7ec4\u6392\u5e8f\uff0c\u7136\u540e\u786e\u5b9a\u4e00\u4e2a\u6700\u5927\u8fb9\uff0c\u7136\u540e\u5728\u5b83\u5de6\u8fb9\u627e\u53e6\u5916\u4e24\u8fb9\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n*log(n) + n^2) = O(n^2) class Solution { public: int triangleNumber(vector&lt;int&gt;&amp; nums) { sort(nums.begin(), nums.end()); int count = 0; for (int i = nums.size() &#8211; 1; i &gt;= 0; &#8211;i) { \/\/ two sum (x + y) &gt; nums[i] int j = 0; int k = i &#8211; 1; while (j &lt; k) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[66],"class_list":["post-2565","post","type-post","status-publish","format-standard","hentry","category-technical","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2565","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2565"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2565\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2565"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2565"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}