Leetcode 15 Solution

This article provides solution to leetcode question 15 (3sum)
Categories:
Tags:
Access this page by simply typing in "lcs 15" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/3sum

Thinking Process

First of all, it’s very unlikely that we can finish this question within O(N) time, because we can’t even do that for the two-sum question. If our target time complexity is O(N^2), it means we can we whatever we want (within O(N^2) time) to simplify the question without increasing the overall time complexity.

That being said, let’s sort the array before we even try to tackle it.

Now the question is to find three numbers in a sorted array that add up to the target. If we fix the first number, we just need to find two numbers in a sorted array, which is even simpler. This is exactly the same question as two-sum-ii-input-array-is-sorted.

So we just have to iterate the first number, and then call the algorithm to address two-sum-ii-input-array-is-sorted.

See, by transforming the question, we completely converted this question to simpler ones, so that no complicated algorithm design is needed here.

Time & Space Complexity

Assuming N is the size of the array

  • Time complexity: O(N^2)
  • Space complexity: O(N)

Solution

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int target = -nums[i];

            int l = i + 1;
            int r = nums.size() - 1;

            while (l < r)
            {
                if (nums[l] + nums[r] < target)
                    l++;
                else if (nums[l] + nums[r] > target)
                    r--;
                else
                {
                    vector<int> a;
                    a.push_back(nums[i]);
                    a.push_back(nums[l]);
                    a.push_back(nums[r]);

                    res.push_back(a);

                    do
                    {
                        l++;
                    } while (nums[l] == nums[l - 1] && l < nums.size());

                    do
                    {
                        r--;
                    } while (nums[r] == nums[r + 1] && r >= 0);
                }
            }
        }

        return res;
    }
};