Clean C++ Solution, O(n^2)


  • 0
    W

    We first sort the array. Then we use ptr1, ptr2 and ptr3 to point to our three numbers. The idea is similar to 3Sum: ptr1 goes through the array from begin to end, while ptr2 (starting at ptr1 + 1) and ptr3 (starting at array end) move to each other till they meet.

    The difference is that, we first keep ptr1 and ptr2 fixed, and keep moving ptr3 so long as the three sum is larger than or equal to target. Once it moves to a position where the three sum is smaller than target, we immediately know that if ptr3 keeps moving left, all the rest three sums will also be smaller than target. Therefore, we immediately add the number of three sums to the result without actually moving ptr3. ptr3 remains at the position where the three sum is first seen smaller than target. After that, we move ptr2 right by one position. Now we can keep moving ptr3 to the left, as said above.

    Since ptr3 never goes back and ptr2 < ptr3, the above step takes time O(n). With ptr1 going through the array once, the overall running time is O(n^2).

    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int ptr1 = 0; ptr1 < nums.size(); ptr1++) {
            int ptr3 = nums.size() - 1;
            for (int ptr2 = ptr1 + 1; ptr2 < nums.size(); ptr2++) {
                while (ptr2 < ptr3 && nums[ptr1] + nums[ptr2] + nums[ptr3] >= target)
                    ptr3--;
                if (ptr3 > ptr2)
                    count += ptr3 - ptr2;
            }
        }
        return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.