Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
3SUM problem
//Title of this code #include <iostream> #include <vector> #include <algorithm> using namespace std; int binarySearch(vector<int> t, int val, int begin, int end) { if (begin > end) return -1; while (begin < end) { int mid = (end - begin) / 2 + begin; if (t[mid] < val) begin = mid + 1; else if (t[mid] > val) end = mid - 1; else return mid; } if (t[begin] == val) return begin; return -1; } void ThreeSumProblem2(vector<int> t) { // copy the vector if (t.size() < 3) return; for (int i = 0; i < t.size(); ++i) t[i] *= t[i]; sort(t.begin(), t.end()); for (int i = 0; i < t.size() - 3; ++i) { for (int j = i + 1; j < t.size() - 2; ++j) { int res = binarySearch(t, t[i] + t[j], j + 1, t.size() - 1); if (res > -1) cout << t[res] << " = " << t[i] << " + " << t[j] << endl; } } } // O(n^3) time complexity void ThreeSumProblem(vector<int>& t) { if (t.size() < 3) return; sort(t.begin(), t.end()); for (int i = 0; i < t.size(); ++i) for (int j = i + 1; j < t.size(); ++j) for (int k = j + 1; k < t.size(); ++k) //if (i != j && j != k && i != k) if (t[k]*t[k] == t[j]*t[j] + t[i]*t[i]){ cout << t[k] << " , " << t[j] << " , " << t[i] << " ---> "; cout << t[k]*t[k] << " = " << t[j]*t[j] << " + " << t[i]*t[i] << endl; } } int main() { vector<int> t; for (int i = 0; i < 20; ++i) t.push_back(i); ThreeSumProblem(t); cout << endl; ThreeSumProblem2(t); }
run
|
edit
|
history
|
help
0
ww999
Search in a rotated sorted array two methods
c++ mouse
cppOverride
Intersected Rectangles
CPP - Arrays - Ex.2
PrintShape
Gauss 4x4 reducido
Dar
shared_ptr deleter