通过前文两数之和算法练手,感觉还好,有了一点做题感觉,
今天看到了这个三数之和的题目,就迫不及待了做了起来
给你一个包含 n 个整数的数组 nums,target,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = target?请你找出所有和为 target且不重复的三元组。
示例 :
输入:nums = [5,12,6,3,9,2,1,7] target= 13 输出:[[5,6,2],[5,1,7],[3,9,1]]
有了前文两数之和题目的铺垫,首先想到了固定某一个值,然后求两数之和为剩余值
比如固定住第一个数字5,然后在其他数字中求两数之和为13-5=8的两个数字
public static List<List<Integer>> threeSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
//两数之和过程
Map<Integer, Integer> data = new HashMap<>();
for (int j = i + 1; j < nums.length; j++) {
int d2 = need - nums[j];
if (data.containsKey(d2)) {
result.add(Arrays.asList(nums[i], nums[j], d2));
}
data.put(nums[j], j);
}
}
return result;
}
这种方式是可以完成此题,但是算法复杂度是O(n²),空间复杂度是O(n)(用于多次构建两数之和map)
同时有点硬靠两数之和解法的嫌疑
缺点是空间复杂度偏大,想办法把空间复杂度降低到O(1)
其实三数之和已经失去了用hash快速定位的优势,如果硬板前面解法反而浪费了空间,需要多次构建hash表
此时不必拘泥于前面的解法
采用排序+双指针解法
public static List<List<Integer>> threeSum2(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
//查找剩余两数之和为need的数字
//由于是已经排序的数组,可以使用头尾两个指针来控制,之和的大小
for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
//如果两数之和大于need,所以右指针左移,也就是向着变小的方向移动k--才有可能找到答案
//如果两数之和小于need,所以左指针右移,也就是向着变大的方向以移动j++
while (j < k && nums[j] + nums[k] > need) {
k--;
}
//遍历结束
if (j == k) {
break;
}
//发现满足条件的答案
if (nums[j] + nums[k] == need) {
result.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
}
return result;
}
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 示例 2:
输入:nums = [] 输出:[] 示例 3:
输入:nums = [0] 输出:[]
这道题完全可以看成,第一道题目三数之和的特殊版本,也就是target=0的版本
换成while循环重写一遍,其实是一样的思路
public static List<List<Integer>> threeSums(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {//去重
continue;
}
int start = i + 1, end = nums.length - 1;
int need = -nums[i];
while (start < end) {
int sum = nums[start] + nums[end];
if (sum > need) {
end--;
} else if (sum < need) {
start++;
} else {
result.add(Arrays.asList(nums[i], nums[start], nums[end]));
while (start < end && nums[start] == nums[start + 1]) {//去重
start++;
}
while (start < end && nums[end] == nums[end - 1]) {//去重
end--;
}
start++;
end--;
}
}
}
return result;
}
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
做了三数之和题目后看到此题目想到的还是用排序+双指针方式,试着把这个思路实现
用了差不多十分钟写的并没有通过,感觉思路还是不顺
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
int nextSum = nums[i] + nums[j] + nums[k];
while (j < k) {
if (Math.abs((target - nextSum)) < Math.abs(target - result)) {
result = nextSum;
}
if (target - nextSum > 0) {
k--;
}
}
}
}
return result;
}
查看下大鹏的题解,真是太漂亮了,思路清晰、逻辑缜密,环环相扣
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
//初始和
int ans = nums[0] + nums[1] + nums[2];
for(int i=0;i<nums.length;i++) {
//双指针
int start = i+1, end = nums.length - 1;
while(start < end) {
int sum = nums[start] + nums[end] + nums[i];
if(Math.abs(target - sum) < Math.abs(target - ans))
ans = sum;
//如果大于目标值,需要左移
if(sum > target)
end--;
//如果小于目标值,需要右移
else if(sum < target)
start++;
else
return ans;
}
}
return ans;
}