题目:
Given an arraySofnintegers, are there elementsa,b,c, anddinSsuch thata+b+c+d=
target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie,a≤b≤c≤d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
翻译:
给定一个整形数组,找出4个数字使得他们的和加起来等于target。
思路:
和3Sum差不多。遍历,保存当前,找到其余三个数值和为target - num[i],然后剩下在用3SUM思路去解决。
代码:
public class Solution {
public static ArrayList<ArrayList<Integer>> fourSum(int[] nums, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.length < 4)
return res;
Arrays.sort(nums);
for(int i = 0; i < nums.length -3;i++)
{
if(i > 0 && nums[i] == nums[i-1])
continue;
ArrayList<ArrayList<Integer>> cur = threeSum(nums,i+1,target-nums[i]); //得到当前数字可以组合出来的数字序列的子集。
for(int j = 0 ;j < cur.size();j++)
{
cur.get(j).add(0, nums[i]);
}
res.addAll(cur);
}
return res;
}
public static ArrayList<ArrayList<Integer>> threeSum(int[] num,int start,int target)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(num == null||num.length<3)//如果只有2个数字 或者为空 返回空
return res;
//Arrays.sort(num);
for(int i = start; i<num.length -2;i++)// 保证最后得有num.length-1 和num.length-2两个数,才可以进循环
{
if(i > start && num[i] == num[i-1])
continue;
ArrayList<ArrayList<Integer>> cur = twoSum(num,i+1,target-num[i]); //得到当前数字可以组合出来的数字序列的子集。
res.addAll(cur);
}
return res;
}
public static ArrayList<ArrayList<Integer>>twoSum (int []num,int start,int target)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(num == null||num.length < 2)
return res;
int l = start;//起始位置
int pri = start-1;//当前数字
int r = num.length-1;//终止位置
while(l < r)//采用夹逼,逼近target
{
if(num[l]+num[r] == target)//
{
ArrayList<Integer> te = new ArrayList<Integer>();//符合的话 把三个数放入到list中
te.add(num[pri]);
te.add(num[l]);
te.add(num[r]);
res.add(te);
int k = l + 1;//从l的下一个开始 去除重复。
while(k < r&& num[k] == num[l])
k++;
l = k;
k = r - 1;//去除R的重复
while(k > l &&num[k] == num[r])
k--;
r = k;
}
else if(num[l] + num[r] > target)//夹逼
r--;
else l++;
}
return res;
}
}
碰到的问题就是在提交的时候,[-2,0,1,-3]和[-3,-2,0,1]竟然不是一样的结果。
明明是一样的数组。后来才发现在
for(int j = 0 ;j < cur.size();j++)
{
cur.get(j).add(0, nums[i]);
}
res.addAll(cur);
这个位置的时候,原来的写法是cur.get(j).add(nums[i]),后来改为上面的写法,把最小的数值插在最前面。
这样提交就OK了。
分享到:
相关推荐
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。 注意: 答案中不可以包
target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 ...
个数字的所有可能组合,并找出满足请求的组合。 这该怎么做? 我们将遍历数组中的每个元素,对于每个元素,我们将搜索其后面的所有数字:是否有 2 个数字之和等于该元素的相反数字? 如果有,请将这两个数字附加到...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 ...
js代码-给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 来源:力扣...
题目描述:在有序数组中找出两个数,使它们的和为 target。 使用双指针,一个指针指向值较小的元素,一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历,指向较大元素的指针从尾向头遍历。 如果两个指针...
target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 add-two-numbers 给出两个 非空 的链表用来表示...
target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 ...
找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 ...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 ...
Sum题目大意:给定一个整数数组,从中找出两个数的下标,使得它们的和等于一个特定的数字。可以假设题目有唯一解。 解题思路: 利用字典idxDict保存数字num到其下标idx的映射,遍历查找数字num与目标数target的...
不会二和整数数组 给定一个整数数组,返回两个数字的索引,使它们相加为特定目标。 您可以假设每个输入都只有一个解决方案,并且您不能两次使用相同的元素。 例子: Given nums = [2, 7, 11, 15], target = 9, ...
给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums...
从数组中找出两个数字使得他们的和是给定的数字 使用一个散列, 存储数字和他对应的索引。然后遍历数组, 如果另一半在散列当中, 那么返回 这两个数的索引, 程序结束;如果不在, 把当前数字加入到散列中。 vector two...
找出数组numbers中的两个数,它们的和为给定的一个数target,并返回这两个数的索引(不需要去重) 思路分析 题目要求说白了就是找出这个给的数组中有哪两个数相加等于目标结果 方法一 很容易想到我们可以遍历两次数组...
target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下 可以假设每种输入只会对应一个答案。但是,不能重复利用这个数组中同样的元素。 Sample 给定 nums = [2, 7, 11, 15], target = 9 因为 ...
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 ...