Of course, we will help you here on SO.
Starting with a new language is never that easy and there may by some things that are not immediately clear in the beginning. Additionally, I do apologize for any rude comments that you may see, but you can be assured that the vast majority of the members of SO are very supportive.
I want to first give you some information on pages like Leetcode and Codeforces and the like. Often also referred to as “competitive programming” pages. Sometimes people misunderstand this and they think that you have only a limited time to submit the code. But that is not the case. There are such competitions but usually not on the mentioned pages. The bad thing is, the coding style used in that real competition events is also used on the online pages. And that is really bad. Because this coding style is that horrible that no serious developer would survive one day in a real company who needs to earn money with software and is then liable for it.
So, these pages will never teach you or guide you how to write good C++ code. And even worse, if newbies start learning the language and see this bad code, then they learn bad habits.
But what is then the purpose of such pages?
The purpose is to find a good algorithm, mostly optimized for runtime execution speed and often also for low memory consumption.
So, the are aiming at a good design. The Language or coding style does not matter for them. So, you can submit even completely obfuscated code or “code golf” solutions, as long at is it fast, it does not matter.
So, do never start to code immediately as a first step. First, think 3 days. Then, take some design tool, like for example a piece of paper, and sketch a design. Then refactor you design and then refactor your design and then refactor your design and then refactor your design and then refactor your design and so one. This may take a week.
And next, search for an appropriate programming language that you know and can handle your design.
And finally, start coding. Because you did a good design before, you can use long and meaningful variable names and write many many comments, so that other people (and you, after one month) can understand your code AND your design.
OK, maybe understood.
Now, let’s analyze your code. You selected a brute force solution with a triple nested loop. That could work for a low number of elements, but will result in most cases in a so called TLE (Time Limit Exceeded) error. Nearly all problems on those pages cannot be solved with brute force. Brute force solutions are always an indicator that you did not do the above design steps. And this leads to additional bugs.
Your code has too major semantic bugs.
You define in the beginning a std::vector with the name “v”. And then, in the loop, after you found a triplet meeting the given condition, you push_back the results in the std::vector. This means, you add 3 values to the std::vector “v” and now there are 3 elements in it. In the next loop run, after finding the next fit, you again push_back 3 additional values to your std::vector ”v” and now there are 6 elements in it. In the next round 9 elements and so on.
How to solve that?
You could use the std::vector’s clear function to delete the old elements from the std::vector at the beginning of the most inner loop, after the if-statement. But that is basically not that good, and, additionally, time consuming. Better is to follow the general idiom, to define variables as late as possible and at that time, when it is needed. So, if you would define your std::vector ”v” after the if statement, then the problem is gone. But then, you would additionally notice that it is only used there and nowhere else. And hence, you do not need it at all.
You may have seen that you can add values to a std::vector by using an initializer list. Something like:
std::vector<int> v {1,2,3};
With that know-how, you can delete your std::vector “v” and all related code and directly write:
ans.push_back( { nums[i], nums[j], nums[k] } );
Then you would have saved 3 unnecessary push_back (and a clear) operations, and more important, you would not get result sets with more than 3 elements.
Next problem. Duplicates. You try to prevent the storage of duplicates by writing && i!=j && i!=k && j!=k. But this will not work in general, because you compare indices and not values and because also the comparison is also wrong. The Boolean expressions is a tautology. It is always true. You initialize your variable j with i+1 and therefore “i” can never be equal to “j”. So, the condition i != j is always true. The same is valid for the other variables.
But how to prevent duplicate entries. You could do some logical comparisons, or first store all the triplets and later use std::unique (or other functions) to eliminate duplicates or use a container that would only store unique elements like a std::set. For the given design, having a time complexity of O(n^3), meaning it is already extremely slow, adding a std::set will not make things worse. I checked that in a small benchmark. So, the only solution is a completely different design. We will come to that later. Let us first fix the code, still using the brute force approach.
Please look at the below somehow short and elegant solution.
vector<vector<int>> threeSum(vector<int>& nums) {
std::set<vector<int>> ans;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (nums[i] + nums[j] + nums[k] == 0)
ans.insert({ nums[i], nums[j], nums[k] });
return { ans.begin(), ans.end() };
}
But, unfortunately, because of the unfortunate design decision, it is 20000 times slower for big input than a better design. And, because the online test programs will work with big input vectors, the program will not pass the runtime constraints.
How to come to a better solution. We need to carefully analyze the requirements and can also use some existing know-how for similar kind of problems.
And if you read some books or internet articles, then you often get the hint, that the so called “sliding window” is the proper approach to get a reasonable solution.
You will find useful information here. But you can of course also search here on SO for answers.
for this problem, we would use a typical 2 pointer approach, but modified for the specific requirements of this problem. Basically a start value and a moving and closing windows . . .
The analysis of the requirements leads to the following idea.
- If all evaluated numbers are > 0, then we can never have a sum of 0.
- It would be easy to identify duplicate numbers, if they would be beneath each other
--> Sorting the input values will be very beneficial.
This will eliminate the test for half of the values with randomly distribute input vectors. See:
std::vector<int> nums { 5, -1, 4, -2, 3, -3, -1, 2, 1, -1 };
std::sort(nums.begin(), nums.end());
// Will result in
// -3, -2, -1, -1, -1, 1, 2, 3, 4, 5
And with that we see, that if we shift our window to the right, then we can sop the evaluation, as soon as the start of the window hits a positive number. Additionally, we can identify immediately duplicate numbers.
Then next. If we start at the beginning of the sorted vector, this value will be most likely very small. And if we start the next window with one plus the start of the current window, then we will have “very” negative numbers. And to get a 0 by summing 2 “very” negative numbers, we would need a very positive number. And this is at the end of the std::vector.
Start with
startPointerIndex 0, value -3
Window start = startPointerIndex + 1 --> value -2
Window end = lastIndexInVector --> 5
And yes, we found already a solution. Now we need to check for duplicates. If there would be an additional 5 at the 2nd last position, then we can skip. It will not add an additional different solution. So, we can decrement the end window pointer in such a case. Same is valid, if there would be an additional -2 at the beginning if the window. Then we would need to increment the start window pointer, to avoid a duplicate finding from that end.
Some is valid for the start pointer index. Example: startPointerIndex = 3 (start counting indices with 0), value will be -1. But the value before, at index 2 is also -1. So, no need to evaluate that. Because we evaluate that already.
The above methods will prevent the creation of duplicate entries.
But how to continue the search. If we cannot find a solution, the we will narrow down the window. This we will do also in a smart way. If the sum is too big, the obviously the right window value was too big, and we should better use the next smaller value for the next comparison.
Same on the starting side of the window, If the sum was to small, then we obviously need a bigger value. So, let us increment the start window pointer. And we do this (making the window smaller) until we found a solution or until the window is closed, meaning, the start window pointer is no longer smaller than the end window pointer.
Now, we have developed a somehow good design and can start coding.
We additionally try to implement a good coding style. And refactor the code for some faster implementations.
Please see:
class Solution {
public:
// Define some type aliases for later easier typing and understanding
using DataType = int;
using Triplet = std::vector<DataType>;
using Triplets = std::vector<Triplet>;
using TestData = std::vector<DataType>;
// Function to identify all unique Triplets(3 elements) in a given test input
Triplets threeSum(TestData& testData) {
// In order to save function oeverhead for repeatingly getting the size of the test data,
// we will store the size of the input data in a const temporary variable
const size_t numberOfTestDataElements{ testData.size()};
// If the given input test vector is empty, we also immediately return an empty result vector
if (!numberOfTestDataElements) return {};
// In later code we often need the last valid element of the input test data
// Since indices in C++ start with 0 the value will be size -1
// With taht we later avoid uncessary subtractions in the loop
const size_t numberOfTestDataElementsMinus1{ numberOfTestDataElements -1u };
// Here we will store all the found, valid and unique triplets
Triplets result{};
// In order to save the time for later memory reallocations and copying tons of data, we reserve
// memory to hold all results only one time. This will speed upf operations by 5 to 10%
result.reserve(numberOfTestDataElementsMinus1);
// Now sort the input test data to be able to find an end condition, if all elements are
// greater than 0 and to easier identify duplicates
std::sort(testData.begin(), testData.end());
// This variables will define the size of the sliding window
size_t leftStartPositionOfSlidingWindow, rightEndPositionOfSlidingWindow;
// Now, we will evaluate all values of the input test data from left to right
// As an optimization, we additionally define a 2nd running variable k,
// to avoid later additions in the loop, where i+1 woild need to be calculated.
// This can be better done with a running variable that will be just incremented
for (size_t i = 0, k = 1; i < numberOfTestDataElements; ++i, ++k) {
// If the current value form the input test data is greater than 0,
// As um with the result of 0 will no longer be possible. We can stop now
if (testData[i] > 0) break;
// Prevent evaluation of duplicate based in the current input test data
if (i and (testData[i] == testData[i-1])) continue;
// Open the window and determin start and end index
// Start index is always the current evaluate index from the input test data
// End index is always the last element
leftStartPositionOfSlidingWindow = k;
rightEndPositionOfSlidingWindow = numberOfTestDataElementsMinus1;
// Now, as long as if the window is not closed, meaning to not narrow, we will evaluate
while (leftStartPositionOfSlidingWindow < rightEndPositionOfSlidingWindow) {
// Calculate the sum of the current addressed values
const int sum = testData[i] + testData[leftStartPositionOfSlidingWindow] + testData[rightEndPositionOfSlidingWindow];
// If the sum is t0o small, then the mall value on the left side of the sorted window is too small
// Therefor teke next value on the left side and try again. So, make the window smaller
if (sum < 0) {
++leftStartPositionOfSlidingWindow;
}
// Else, if the sum is too biig, the the value on the right side of the window was too big
// Use one smaller value. One to the left of the current closing address of the window
// So, make the window smaller
else if (sum > 0) {
--rightEndPositionOfSlidingWindow;
}
else {
// Accodring to above condintions, we found now are triplet, fulfilling the requirements.
// So store this triplet as a result
result.push_back({ testData[i], testData[leftStartPositionOfSlidingWindow], testData[rightEndPositionOfSlidingWindow] });
// We know need to handle duplicates at the edges of the window. So, left and right edge
// For this, we remember to c
const DataType lastLeftValue = testData[leftStartPositionOfSlidingWindow];
const DataType lastRightValue = testData[rightEndPositionOfSlidingWindow];
// Check left edge. As long as we have duplicates here, we will shift the opening position of the window to the right
// Because of boolean short cut evaluation we will first do the comparison for duplicates. This will give us 5% more speed
while (testData[leftStartPositionOfSlidingWindow] == lastLeftValue && leftStartPositionOfSlidingWindow < rightEndPositionOfSlidingWindow)
++leftStartPositionOfSlidingWindow;
// Check right edge. As long as we have duplicates here, we will shift the closing position of the window to the left
// Because of boolean short cut evaluation we will first do the comparison for duplicates. This will give us 5% more speed
while (testData[rightEndPositionOfSlidingWindow] == lastRightValue && leftStartPositionOfSlidingWindow < rightEndPositionOfSlidingWindow)
--rightEndPositionOfSlidingWindow;
}
}
}
return result;
}
};
The above solution will outperform 99% of other solutions. I made many benchmarks to prove that.
It additionally contains tons of comments to explain what is going on there. And If I have selected “speaking” and meaningful variable names for a better understanding.
I hope, that I could help you a little.
And finally: I dedicate this answer to Sam Varshavchik and PaulMcKenzie.
