AC O(n^2) Java solution


  • 0
    J
    public int threeSumSmaller(int[] nums, int target) {
        int len = nums.length;
        if(len < 3) return 0;
        Arrays.sort(nums);
        int count = 0;
        for(int i=0; i<nums.length-2; i++) {
            int j = i + 1;
            while(j < len && nums[i] + 2 * nums[j] < target) {
                j++;
            }
            j--;				// any two elements within i to j will satisfy the condition
            count += (j-i-1)*(j-i)/2;
            for(int k=j+1; k<len; k++) {        // k go up, j go down
            	while(j > i && nums[i] + nums[j] + nums[k] >= target) {
            		j--;
            	}
            	count += j-i;
            }
        }
        return count;
    }
    

    We already know that any two elements from i to j along with i itself is added to our count, now we need to go up to see if there's more triplets when one element is bigger than nums[j]. So we let k start from j+1 to len and let j decrement to i. In each position, we check if current j and k satisfy the condition. If it does, that means all elements between i and current j along with current k can be added to the count. Then we can increment k to see if current j still satisfy the condition. If it doesn't, we decrement j until it does.

    So for each i, the runtime is O(n) because we at most access each position twice (once when we find the appropriate j, another when j decrement all the way down from that position), thus the total runtime is O(n^2).


Log in to reply
 

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