Accepted and Simple Java O(n^2) solution with detailed explanation


  • 57
    K

    We sort the array first. Then, for each element, we use the two pointer approach to find the number of triplets that meet the requirements.

    Let me illustrate how the two pointer technique works with an example:

    target = 2
    
      i  lo    hi
    [-2, 0, 1, 3]
    

    We use a for loop (index i) to iterate through each element of the array. For each i, we create two pointers, lo and hi, where lo is initialized as the next element of i, and hi is initialized at the end of the array. If we know that nums[i] + nums[lo] + nums[hi] < target, then we know that since the array is sorted, we can replace hi with any element from lo+1 to nums.length-1, and the requirements will still be met. Just like in the example above, we know that since -2 + 0 + 3 < 2, we can replace hi (3) with 1, and it would still work. Therefore, we can just add hi - lo to the triplet count.

    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            int result = 0;
            Arrays.sort(nums);
            for(int i = 0; i <= nums.length-3; i++) {
                int lo = i+1;
                int hi = nums.length-1;
                while(lo < hi) {
                    if(nums[i] + nums[lo] + nums[hi] < target) {
                        result += hi - lo;
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
            return result;
        }
    }

  • 0
    H

    Neat and great comments

    Thankyou


  • 0
    Y

    great explanation! thanks for taking your time.


  • 0
    Y

    really elegant solution, endorse you!


  • 0
    D

    Explanations are amazing! Good work keep it up


  • 0
    S

    I'm really fond of your explanation! Great job!


  • 0
    L

    Thanks for the explanation man!!! 😘😘


  • 3

    @kevinhsu said in Accepted and Simple Java O(n^2) solution with detailed explanation:

    If we know that nums[i] + nums[lo] + nums[hi] < target, then we know that since the array is sorted, we can replace hi with any element from lo+1 to nums.length-1, and the requirements will still be met.

    Thanks for your solution!!

    One thing I don't quite understand is that
    why
    replacing hi with any element from lo+1 to nums.length-1 can still meet the requirement
    but not
    replacing hi with any element from lo+1 to hi-1 ?

    since numbers between hi+1 to nums.length-1 is greater than hi, replacing hi with these numbers would not be smaller than target.

    Thanks!


  • 0
    P

    I understood adding high-low to result but in that case why still increment low++ ? cant we move to next i


Log in to reply
 

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