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?

解法1： O(N^2)

O(N^2)的解法和3Sum或者3Sum closest类似，但比较tricky的地方是，在用双指针left和right找到一个<target的数的时候，其实right 和left之间所有的数都满足要求（排序之后）。所以这个时候我们把right-left加入到res中，然后更新left即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    cnt += right - left;    // trick is here
                    left++;
                } else {
                    right--;
                }
            }
        }
        return cnt;
    }
}