15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
先对其排序，外层是一个数，内层其实就是两个数的sum, 然后通过双指针前后来判断，代码如下：
// Time O(n^2)
// Space O(n);
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//corner case;
if(nums == null || nums.length == 0) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums); // notice, firstly need sort;
for(int i = 0; i < nums.length - 2; i++) { // i < nums.length - 2;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int low = i + 1, high = nums.length - 1, sum = 0 - nums[i];
while(low < high) {
if(nums[low] + nums[high] == sum) {
res.add(Arrays.asList(nums[low], nums[high], nums[i]));
while(low < high && nums[low] == nums[low + 1]) low++; // notice this place is "low + 1";
while(low < high && nums[high] == nums[high - 1]) high--;
low++;
high--;
}else if(nums[low] + nums[high] < sum) {
low++;
}else {
high--;
}
}
}
return res;
}
}
16. 3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
//Java solution
class Solution {
public int threeSumClosest(int[] nums, int target) {
//Arrays.sort()是O(nlogn)的，只要是基于比较的排序算法都是不低于nlogn的
Arrays.sort(nums);
int closest = nums[0] + nums[1] + nums[2];
for(int i = 0; i < nums.length; i++) {
int low = i + 1, high = nums.length - 1;
while(low < high) {
int newClosest = nums[i] + nums[low] + nums[high];
int remain = target - newClosest;
if(remain > 0) {
low++;
}else if(remain < 0) {
high--;
}else {
return target;
}
closest = Math.abs(target - closest) < Math.abs(target - newClosest) ? closest : newClosest;
}
}
return closest;
}
}
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.
Example:
Input: nums = [-2,0,1,3], and target = 2
Output: 2
Explanation: 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?
思路：
Let us try sorting the array first. For example, nums = [3,5,2,8,1] becomes[1,2,3,5,8].
Let us look at an example nums=[1,2,3,5,8], and target = 7.
[1, 2, 3, 5, 8]
↑ ↑
left right
Let us initialize two indices, left and right pointing to the first and last element respectively.
When we look at the sum of first and last element, it is 1 + 8 = 9, which is ≥ target. That tells us no index pair will ever contain the index right. So the next logical step is to move the right pointer one step to its left.
[1, 2, 3, 5, 8]
↑ ↑
left right
Now the pair sum is 1+5=6, which is < target. How many pairs with one of the index = left that satisfy the condition? You can tell by the difference between right and left which is 3, namely (1,2), (1,3), and (1,5). Therefore, we move left one step to its right.
class Solution {
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;
}
public int twoSumSmaller(int[] nums, int startIndex, int target) {
int low = startIndex;
int high = nums.length - 1;
int sum = 0;
while(low < high) {
if(nums[low] + nums[high] < target) {
sum += high - low;
low++;
}else {
high--;
}
}
return sum;
}
}
