有效三角形的个数

 

611. 有效三角形的个数 - 力扣（LeetCode）

暴力解法 :

// 有效三角形: a + b > c
    public int triangleNumber(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                int b = nums[j];
                for (int k = j + 1; k < nums.length; k++) {
                    int c = nums[k];
                    if (checkTriangle(a, b, c)) {
                        count += 1;
                    }
                }
            }
        }
        return count;
    }
    public boolean checkTriangle(int a, int b, int c) {
        if (a + b > c && a + c > b && b + c > a) {
            return true;
        }
        return false;
    }

这里对 数组进行排序可以通过暴力过

这里我们对数组进行排序，那么就可以考虑使用 二分查找来优化这个暴力枚举.

图二:

class Solution {
    public int triangleNumber(int[] nums) {
        // 对 数组进行排序操作 , 二分查找的基础就是仔有序的数组
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                int b = nums[j];
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    int mid = (left + right + 1) / 2;
                    int c = nums[mid];
                    if (a + b <= c) {
                        right = mid - 1;
                    } else {
                        // 此时 mid 到 left 之前的数都是满足的
                        left = mid;
                    }
                }
                // 走到这里判断一下,并把满足的三角形个数添加上
                if (left < nums.length && nums[left] < a + b) {
                    count += left - j;
                }
            }
        }
        return count;
    }
}

最优解 : 单调性 + 双指针

图一：

图二:

代码

class Solution {
    public int trianglez`Number(int[] nums) {
        int count = 0;
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            int c = nums[i];
            while (left < right) {
                if (nums[right] + nums[left] > c) {
                    // 此时都是满足情况的,更改 right 的位置
                    count += right - left;
                    right--;
                } else {
                    // 此时不满足情况
                    left++;
                }
            }
        }
        return count;
    }
}

python:

class Solution(object):
    def triangleNumber(self, nums):
        # 计数器
        count = 0
        # 排序
        nums.sort()
        for i in range(len(nums), -1):
            left = 0
            right = len(nums) - 1
            c = nums[i]
            while left < right:
                if nums[left] + nums[right] > c:
                    # 此时数都满足
                    count += right - left
                    # 更改 right
                    right -= 1
                else:
                    # 此时 <= c 直接让 left 更改即可
                    left += 1
        return count

 

查找总价格为目标值的两个商品

 

查找总价格为目标值的两个商品

这道题是非常简单的， 我们可以使用暴力枚举或者双指针来写 .

 

暴力枚举:

  public int[] twoSum(int[] price, int target) {
        for (int i = 0; i < price.length; i++) {
            int number1 = price[i];
            for (int j = i + 1; j < price.length; j++) {
                int number2 = price[j];
                if (number1 + number2 == target) {
                    return new int[]{number1, number2};
                }
            }
        }
        return new int[]{};
    }

 

既然暴力过不了，那么我们来优化一下，数组是有序的那么我们可以使用二分查找进行优化

class Solution {
    public int[] twoSum(int[] price, int target) {
        for (int i = 0; i < price.length; i++) {
            int number = price[i];
            int left = i + 1;
            int right = price.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                int number2 = price[mid];
                if (number + number2 < target) {
                    // 数组有序 当前 mid 位置都小于 target 那么 mid 之前的同样小于直接让 left 改变
                    left = mid + 1;
                } else if (number + number2 > target) {
                    right = mid - 1;
                } else {
                    // 此时找到了
                    return new int[] { price[i], price[mid] };
                }
            }
        }
        return new int[] {};
    }
}

 

暴力 ，二分，使用了 下面我们来使用最优的解法 即 双指针.

class Solution {
    public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length - 1;
        while (left < right) {
            int number = price[left] + price[right];
            if (number < target) {
                left++;
            } else if (number > target) {
                right--;
            } else {
                // 此时找到了
                return new int[] { price[left], price[right] };
            }
        }
        return new int[] {};
    }
}

 

python:

class Solution(object):
    def twoSum(self, price, target):
        left = 0
        right = len(price) - 1
        while left < right:
            if price[left] + price[right] > target:
                right -= 1
            elif price[left] + price[right] < target:
                left += 1
            else:
                return [price[left], price[right]]
        return []