一定数目的点或圆在等距离的排列下可以形成一个等边三角形这样的数被称为三角形数。前6个三角形数分别为136101521。给定一个正整数 x请你判断 x 能否表示为两个三角形数可以相同的和。c++最大数据10^9限时1s

可以使用双指针的方法来解决这个问题。

首先，我们可以先生成一个三角形数的数组，数组中的每个元素都是一个三角形数。可以使用一个循环来计算每个三角形数，直到超过给定的最大值x为止。

接下来，我们使用双指针的方法，从数组的两端开始遍历，判断两个指针指向的元素之和是否等于x。如果等于x，则返回true；如果小于x，则将左指针右移一位；如果大于x，则将右指针左移一位。直到两个指针相遇为止。

如果循环结束后仍然没有找到满足条件的两个三角形数之和等于x，则返回false。

下面是相应的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

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

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

    return false;
}

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

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