时间戳

首页 > 解决方案 > 对于非常大的输入，从 1...n 中丢失和重复的数字数组。使用 1...n 系列的属性的解决方案。溢出问题

c++ - 对于非常大的输入，从 1...n 中丢失和重复的数字数组。使用 1...n 系列的属性的解决方案。溢出问题

问题描述

这是同一网站为https://www.interviewbit.com/problems/repeat-and-missing-number-array/提供的代码：

vector<int> repeatedNumber(const vector<int> &V) {
   long long sum = 0;
   long long squareSum = 0;
   long long temp;
   for (int i = 0; i < V.size(); i++) {
       temp = V[i];
       sum += temp;
       sum -= (i + 1);
       squareSum += (temp * temp);
       squareSum -= ((long long)(i + 1) * (long long)(i + 1));
   }
   // sum = A - B
   // squareSum = A^2 - B^2 = (A - B)(A + B)
   // squareSum / sum = A + B
   squareSum /= sum;

   // Now we have A + B and A - B. Lets figure out A and B now. 
   int A = (int) ((sum + squareSum) / 2);
   int B = squareSum - A;

   vector<int> ret;
   ret.push_back(A);
   ret.push_back(B);
   return ret;
}

现在，我编写了一个类似的代码，但没有进行类型转换，并且对于较大的输入它会返回错误。谁能解释类型转换如何解决溢出问题？

另外，我看到了这个问题的 XOR 方法，但我不知道位操作问题。如果有人可以帮助我提供一些链接/资源来使用位操作方法处理问题，那就太好了！

感谢您阅读我的问题并希望提供帮助！干杯!

标签： c++arraysoverflow

解决方案

(i + 1) * (i + 1)将在int算术中评估，有可能溢出，其行为是undefined。

写作

((long long)(i + 1) * (long long)(i + 1));

是一种避免这种影响的冗长方法；你可以使用更清晰的

(i + 1LL) * (i + 1)

相反，这会导致其他术语的转换。

推荐阅读