题解 | #小红的最小三角形周长#

从数组中寻找周长最小的三角形，常规的思路是先排序，再从小到大依次搜索，再添加一些小优化就OK了。

假设最短三角形的三条边依次是a、b、c（a<b<c），通过分析我们可以知道，b、c在排序后的数组中一定是相邻的，因为如果b、c中间还有数据（设为x），那么a、b、x会形成一个更短的三角形，与假设矛盾。

如此，我们仅需将c设为遍历变量，便可以直接确定b，接下来只需要找到a就可以了，根据三角形性质，我们有a>c-b，借助二分查找法我们可以查找到0~b范围内比c-b大的最小值，这个值就是我们要的a。

需要注意的是，从左到右按以上逻辑遍历数组查找到的第一组数据，不一定是最终结果（最优解），因为以上算法实际上仅能保证b+c是最小的，而不能保证b+c+a也是最小的，考虑一个实际例子：2,88,90,100,101，我们查找到的第一组数据是88,90,100，周长为278，但实际上答案是2,100,101，周长为203，因此我们还要继续遍历，看看后面有没有更短的三角形。

后续遍历的终止条件是已有周长<2c+1，因为当我们确定c时，由它所构成的三角形的最短周长为：c+b+(c-b+1)=2c+1，这个值越往后遍历越大，因此当2c+1比已知的答案更大时，便没有继续遍历的必要了。

参考代码如下，由于题目已经保证了数据的合法性，因此这里忽略了很多合法性检查：

class Solution {
  public:
    //使用二分法寻找三条边中最小的边，第21行的条件保证了该边一定存在
    int find_shortest_edge(vector<int>& nums, int endIdx, int minLimit) {
        int leftIdx = 0, rightIdx = endIdx, mid = 0;
        while (leftIdx < rightIdx) {
            mid = (leftIdx + rightIdx) / 2;
            if (nums[mid] < minLimit) leftIdx = mid + 1;
            else if (nums[mid] >= minLimit) rightIdx = mid;
        }
        return nums[leftIdx];
    }
  
    int hongstriangle(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        unsigned int shortestPerimeter = UINT32_MAX;
        unsigned int currPerimeter = 0;
        for (int i = 2; shortestPerimeter == UINT32_MAX || (i < nums.size() &&
                shortestPerimeter > 2 * nums[i]); i++) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                currPerimeter = nums[i] + nums[i - 1] + find_shortest_edge(nums, i - 2,
                                nums[i] - nums[i - 1] + 1);
                if (currPerimeter < shortestPerimeter) {
                    shortestPerimeter = currPerimeter;
                }
            }
        }
        return shortestPerimeter;
    }
};