?LeetCode刷題實戰(zhàn)259：較小的三數(shù)之和
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.
示例
示例：
輸入: nums = [-2,0,1,3], target = 2
輸出: 2
解釋: 因為一共有兩個三元組滿足累加和小于 2:
[-2,0,1]
[-2,0,3]
進階：是否能在 O(n2) 的時間復(fù)雜度內(nèi)解決？
解題
public class Solution {
public int threeSumSmaller(int[] nums, int target) {
// 先將數(shù)組排序
Arrays.sort(nums);
int cnt = 0;
for(int i = 0; i < nums.length - 2; i++){
int left = i + 1, right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
// 如果三個數(shù)的和大于等于目標數(shù)，那將尾指針向左移
if(sum >= target){
right--;
// 如果三個數(shù)的和小于目標數(shù)，那將頭指針向右移
} else {
// right - left個組合都是小于目標數(shù)的
cnt += right - left;
left++;
}
}
}
return cnt;
}
}