BiruLyu
8/5/2017 - 10:32 PM

## 259. 3Sum Smaller(#).java

``````public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length - 2; i++) {
sum += twoSumSmaller(nums, i + 1, target - nums[i]);
}
return sum;
}

private int twoSumSmaller(int[] nums, int startIndex, int target) {
int sum = 0;
int left = startIndex;
int right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
sum += right - left;
left++;
} else {
right--;
}
}
return sum;
}``````
``````public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length - 2; i++) {
sum += twoSumSmaller(nums, i + 1, target - nums[i]);
}
return sum;
}

private int twoSumSmaller(int[] nums, int startIndex, int target) {
int sum = 0;
for (int i = startIndex; i < nums.length - 1; i++) {
int j = binarySearch(nums, i, target - nums[i]);
sum += j - i;
}
return sum;
}

private int binarySearch(int[] nums, int startIndex, int target) {
int left = startIndex;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] < target) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}

``````
``````public class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length < 3) return 0;
Arrays.sort(nums);
int len = nums.length;
int cnt = 0;
for (int i = 0; i < len - 2; i++) {
//if (nums[i] >= target) return cnt; //wrong answer for case : [-1,1,-1,-1] -1
//if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1;
int k = len - 1;
while (j < k) {
// if (j > i + 1 && nums[j] == nums[j - 1]) { // needn't to remove duplication
//     j++;
//     continue;
// }
int sum = nums[i] + nums[j] + nums[k];
if (sum < target) {
cnt += k - j;
j++;
} else {
k--;
}
}
}
return cnt;
}
}``````