Question

Formatted question description: https://leetcode.ca/all/259.html

 259	3Sum Smaller

 Given an array of n integers nums and a target,
 find the number of index triplets i, j, k with 0 <= i < j < k < n
    that satisfy the condition nums[i] + nums[j] + nums[k] < target.

 For example, given nums = [-2, 0, 1, 3], and target = 2.

 Return 2. Because there are two triplets which sums are less than 2:

 [-2, 0, 1]
 [-2, 0, 3]

 Follow up:
 Could you solve it in O(n^2) runtime?

 @tag-array

Algorithm

The follow up in the title allows us to achieve it within O(n^2) time complexity. Then learn from the methods in the previous two questions 3Sum Closest and 3Sum, and use double pointers to do it.

There is a trick here that is to judge When the sum of three numbers is less than the target value, right-left should be added to the result at this time, because after the array is sorted, if the addition of num[right] is less than the target value, then adding a smaller number must also be less than Target value, then move the left pointer to the right by one place, otherwise move the right pointer to the left by one place,

Code

Java

public class Three_Sum_Smaller {

    // time: O(N^2)
    // space: O(1)
    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {

            if(nums == null || nums.length == 0) {
                return 0;
            }

            Arrays.sort(nums);

            int count = 0;
            for(int i = 0; i < nums.length - 2; i++) {
                int lo = i + 1, hi = nums.length - 1;
                while(lo < hi) {
                    if(nums[i] + nums[lo] + nums[hi] < target) {
                        count += hi - lo; // adding a smaller number must also be less than Target value
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }

            return count;
        }
    }
}

All Problems

All Solutions