首页 > 代码库 > LeetCode-3Sum Smaller

LeetCode-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(n2) runtime?

Solution:

public class Solution {    public int threeSumSmaller(int[] nums, int target) {        if (nums.length<3) return 0;        Arrays.sort(nums);                int count = 0;        for (int p1=0;p1<nums.length-2;p1++){            // Early termination            if (nums[p1]+nums[p1+1]+nums[p1+2]>=target) break;                        int p2=p1+1, p3=nums.length-1;            while (p2<p3){                while (p2<p3 && nums[p2]+nums[p3]>=target-nums[p1]){                    p3--;                }                count += p3-p2;                p2++;            }        }        return count;    }}

 

 
 
 
 
 

 

LeetCode-3Sum Smaller