My code:
public class Solution {
public int threeSumSmaller(int[] nums, int target) {
int ret = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int begin = i + 1;
int end = nums.length - 1;
int tar = target - nums[i];
while (begin < end) {
int sum = nums[begin] + nums[end];
if (sum < tar) {
ret += end - begin;
begin++;
}
else {
end--;
}
}
}
return ret;
}
}
一开始我是拿brute force来求解的。
后来突然想起来了可以排序。然后这个做法就自然而然出来了。
reference:
https://leetcode.com/articles/3sum-smaller/
还有种做法就是用binary search,
定住 i,j, binary search k so that nums[k] < target - nums[i] - nums[j]
find the biggest k
注意这里写binary search, mid = (begin + end + 1) / 2;
以防止进入死循环。
Anyway, Good luck, Richardo! -- 09/05/2016
