LeetCode Valid Triangle Number Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1:
Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3Note:
- The length of the given array won’t exceed 1000.
- The integers in the given array are in the range of [0, 1000].
给定一个数组，问从中能取出所少个三元数组，使得取出的三个数能构成一个三角形。 首先明确三条线段构成三角形的条件是任意两边之和要大于第三遍。 先上暴力，直接dfs枚举出所有的三元组，判断能构成三角形，则方案数加1。代码如下： [cpp] class Solution { private: void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ++ans; //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { int ans = 0; vector<int> cand; sort(nums.begin(), nums.end()); dfs(ans, nums, cand, 0); return ans; } }; [/cpp] 本代码提交TLE：219 / 243。数组最大长度是1000，则所有的组合数有1000*999*998=997002000，确实有点大。。。 后来我发现，报TLE的大数据，虽然有1000个数，但是有很多都是重复的，真正不同的数大概只有100个左右。所以我就想，先对数据去重，在所有互异的数中dfs。然后根据每条边重复的次数来求组合数。 比如样例中，互异的数是[2,3,4]，dfs发现[2,3,4]可以构成三角形，则所有由[2,3,4]构成的三角形的个数应该是count[2]*count[3]*count[4]=2*1*1=2。 所以我们先对数组做个hash，统计数值及其出现频率的关系。注意，因为边的长度最大也只为1000，所以用一个1000长的数组来hash比用map或者unordered_map占用的内存更少，否则会MLE。 然后分三类情况进行计算：1. 三条边互不相同；2.有两条边的值相等；3.三条边的值都相等。 其中第一种情况用常规的DFS求解。第二种和第三种情况就是简单的枚举。 还需要注意一点是，边长为0的值需要过滤掉。 完整代码如下： [cpp] class Solution { private: void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ans += count[a] * count[b] * count[c]; // 三边各异 //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, count, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { vector<int> mii(1001, 0); for (const auto& i : nums)++mii[i]; // hash vector<int> distinct; for (int i = 1; i < 1001; ++i) { if (mii[i] > 0)distinct.push_back(i); } int ans = 0; vector<int> cand; dfs(ans, mii, distinct, cand, 0); // 三边互不相同 int n = distinct.size(); for (int i = 0; i < n; ++i) { if (mii[distinct[i]] >= 3) { // 三边相同 int &d = mii[distinct[i]]; ans += (d*(d – 1)*(d – 2)) / 6; } for (int j = i + 1; j < n; ++j) { if (mii[distinct[i]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[i], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[a] * (mii[a] – 1) / 2)*mii[c]; } } if (mii[distinct[j]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[j], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[b] * (mii[b] – 1) / 2)*mii[a]; } } } } return ans; } }; [/cpp] 本代码提交AC，用时1589MS。]]>