Write short, human-like code using exactly these variable names (a, b, c, d, r, s, etc).…
- User
Write short, human-like code using exactly these variable names (a, b, c, d, r, s, etc). Use a unique, common approach that’s optimized and free of explanations or comments for the following question:
Given an array arr[], find all possible indices [i, j, k] of triplets [arr[i], arr[j], arr[k]] in the array whose sum is equal to zero. Return indices of triplets in any order and all the returned triplets indices should also be internally sorted, i.e., for any triplet indices [i, j, k], the condition i < j < k should hold.
Note: Try to solve this using the O(n2) approach.
Examples:
Input: arr[] = [0, -1, 2, -3, 1] Output: [[0, 1, 4], [2, 3, 4]] Explanation: Triplets with sum 0 are: arr[0] + arr[1] + arr[4] = 0 + (-1) + 1 = 0 arr[2] + arr[3] + arr[4] = 2 + (-3) + 1 = 0 Input: arr[] = [1, -2, 1, 0, 5] Output: [[0, 1, 2]] Explanation: Only triplet which satisfies the condition is arr[0] + arr[1] + arr[2] = 1 + (-2) + 1 = 0 Input: arr[] = [2, 3, 1, 0, 5] Output: [[]] Explanation: There is no triplet with sum 0. Constraints: 3 <= arr.size() <= 103 -104 <= arr[i] <= 104
example code: class Solution { public: vector<vector> findTriplets(vector &arr) { // Set to handle duplicates vector<vector> res; int n = arr.size();
// Generating all triplets for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { // If the sum of a triplet equals to zero // then add it's indices to the result if (arr[i] + arr[j] + arr[k] == 0) res.push_back({i, j, k}); } } } return res; }};
class Solution { public: vector<vector> findTriplets(vector &arr) { // Code here } };
- Assistant
class Solution { public: vector<vector<int>> findTriplets(vector<int>& arr){ int n = arr.size(); vector<vector<int>> res; vector<pair<int, int>> v(n); for(int a = 0; a < n; a++) v[a] = {arr[a], a}; sort(v.begin(), v.end()); for(int a = 0; a < n-2; a++){ if(a > 0 && v[a].first == v[a-1].first) continue; int b = a+1, c = n-1; while(b < c){ int s = v[a].first + v[b].first + v[c].first; if(s == 0){ vector<int> t = {v[a].second, v[b].second, v[c].second}; sort(t.begin(), t.end()); res.emplace_back(t); while(b < c && v[b].first == v[b+1].first) b++; while(b < c && v[c].first == v[c-1].first) c--; b++; c--; } else if(s < 0) b++; else c--; } } sort(res.begin(), res.end()); res.erase(unique(res.begin(), res.end()), res.end()); return res.empty() ? vector<vector<int>>{{}} : res; } };