*Java* straightforward O(n^2) solution with explanations

  • 13

    Similar to 3-sum problem, we sort the array first. Again, similar to 3-sum problem, we use two pointers (lo and hi) to check if the sum satisfies the condition. The only trick here is that if we found out

    nums[i] + nums[lo] + nums[hi] < target

    then for all hi in (lo, hi] satisfy the condition. That's why we have

    count += hi-lo;

    in the code.

    Code in Java:

    public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int L = nums.length;
        int count = 0;
        for(int i=0; i<L-2; i++) {
    		int lo = i+1;
    		int hi = L-1;
    		while(lo<hi) {
    			if(nums[i] + nums[lo] + nums[hi] < target) {
    				count += hi-lo;
        return count;

  • 0

Log in to reply

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