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

思路: 3Sum的变种,要求统计三个数的和小于给定target的次数。先排序,然后用外层循环来确定第一个数, 内层循环用左右指针从两头往中间寻找。得到三个数的和,如果和大于等于target,说明找大了, right指针往左移动;如果找到的和小于target,我们取right-left的差值即为有效结果。 为什么呢? 假设left不动,那那么right像左移,直到重合之前的前一点都属于有效结果。

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length < 3) return 0;
        Arrays.sort(nums);
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            int first = nums[i];    
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = first + nums[left] + nums[right];
                if (sum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s