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


  • 13
    E

    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;
        Arrays.sort(nums);
        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;
    				lo++;
    			}
    			else
        			hi--;
    		}
        }
        return count;
    }
    }

  • 0
    P

Log in to reply
 

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