给定一个正整数 x请你判断 x 能否表示为两个三角形数可以相同的和。c++最大数据为10^9时间限制1s

题目要求判断一个正整数x能否表示为两个三角形数（可以相同）的和。

首先，我们需要了解什么是三角形数。一个数n是三角形数，当且仅当存在一个正整数k，使得n = k * (k + 1) / 2。我们可以通过遍历正整数k，计算k * (k + 1) / 2的值，将结果保存在一个数组中，以便后续的查找操作。

接下来，我们可以使用双指针的方法来判断x能否表示为两个三角形数的和。我们使用两个指针i和j，分别指向三角形数数组的开头和结尾。如果三角形数数组中i和j指向的两个数的和等于x，则x可以表示为两个三角形数的和。如果三角形数数组中i和j指向的两个数的和小于x，则将i指针向右移动一位。如果三角形数数组中i和j指向的两个数的和大于x，则将j指针向左移动一位。直到找到满足条件的两个数或者i和j指针相遇为止。

下面是使用C++实现的代码：

#include <iostream>
#include <vector>

using namespace std;

bool isTriangleNumber(int n) {
    int left = 1, right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long long num = (long long)mid * (mid + 1) / 2;
        if (num == n) {
            return true;
        } else if (num < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

bool canRepresentAsTriangleNumbers(int x) {
    vector<int> triangleNumbers;
    int k = 1;
    while (true) {
        int triangleNumber = k * (k + 1) / 2;
        if (triangleNumber > x) {
            break;
        }
        triangleNumbers.push_back(triangleNumber);
        k++;
    }

    int i = 0, j = triangleNumbers.size() - 1;
    while (i <= j) {
        int sum = triangleNumbers[i] + triangleNumbers[j];
        if (sum == x) {
            return true;
        } else if (sum < x) {
            i++;
        } else {
            j--;
        }
    }
    return false;
}

int main() {
    int x;
    cin >> x;
    if (canRepresentAsTriangleNumbers(x)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

该算法的时间复杂度为O(sqrt(x))，可以在给定的时间限制内解决问题