Leetcode discuss: 259. 3Sum Smaller

Jan. 30, 2021

Here is the link. 

C# | Sorting | two pointer sliding window

Jan. 30, 2021
It is easy to write a brute force solution using O(N^3), N is the length of the array.

In order to lower the time complexity to O(N^2), I thought about a few minutes, and it is hard to figure out any given two numbers in the array, how many numbers are available for k - twoSum starting from given index in the array, whereas twoSum is the sum of the first two numbers. It is hard to come out O(1). One of ideas is to preprocess the array and try to explore the absolute value's upper bound value 100 in the array.

I think that it is better to sort the array, and then the problem should be easier to come out.

Case study
Input: nums = [-2,0,1,3], target = 2
Output: 2
Sort the array, so the sorted array is [-2, 0, 1, 3].
Work on three numbers, first number index's variable first = 0, second variable = 1, third = 3, since 0 + 3 = 3 < target - (-2) = 4, so second = 1, there are two options for the third number. Add two to count variable.

Next move second variable to 2. Skip rest of steps. 

public class Solution {
    public int ThreeSumSmaller(int[] nums, int target) 
    {
        int count = 0;
        Array.Sort(nums);
        var length = nums.Length;
    
        for(int first = 0; first < length - 2; first++) 
        {
            var second = first  + 1;
            var third  = length - 1;
            
            while(second < third) 
            {
                if(nums[first] + nums[second] + nums[third] < target) 
                {
                    count += third - second;
                    second++;
                } 
                else 
                {
                    third--;
                }
            }
        }
        
        return count;
    }
}