leetcode:两数之和，三数之和
两数之和
题目：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> maps = new HashMap<>();
for(int i =0;i<nums.length;i++){
if(maps.containsKey(target - nums[i])){
return new int[]{maps.get(target- nums[i]),i};
}else{
maps.put(nums[i],i);
}
}
return null;
}和为定值子集组合
题目具体是这样的，给定n个数字，比如{2,6,1,7,4,9}，并给定一个SUM，比如SUM=20，在上述这6个数字中，挑出一些，使得他们的和等于SUM，把所有的组合都找出来。我们这个例子的结果就是：
1 + 2 + 4 + 6 + 7 = 20
1 + 4 + 6 + 9 = 20
4 + 7 + 9 = 20
- 给一个指定的数和一个数组，如何找到该数组中所有相加等于该数的组合。
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test40 {
public static void main(String[] args) {
int[] candidates = {2,6,1,7,4,9};
System.out.println(combinationSum2(candidates,20));
}
static List<List<Integer>> lists = new ArrayList<>();
public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
//对数组进行排序 这个很关键
if (candidates == null || candidates.length == 0 || target < 0) {
return lists;
}
List<Integer> list = new ArrayList<>();
dfs(list, candidates, target, 0);
return lists;
}
private static void dfs(List<Integer> list, int[] candidates, int target, int start) {
//递归的终止条件
if (target < 0) {
return;
}
if (target == 0) {
lists.add(new ArrayList<>(list));
} else {
for (int i = start; i < candidates.length; i++) {
//因为这个数和上个数相同，所以从这个数开始的所有情况，在上个数里面都考虑过了，需要跳过
if (i != start && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
dfs(list, candidates, target - candidates[i], i + 1);
list.remove(list.size() - 1);
//归去来兮
}
}
}
}
组合总和2
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates =
[2,3,6,7],
target =
7
,
所求解集为:
[
[7],
[2,2,3]
]
/*
* @Author liuhaidong
* @Description 该程序的思路
* 2 2 2 2
* 2 2 2
* 2 2 3
*
* @Date 15:51 2019/9/25 0025
**/
static List<List<Integer>> lists = new ArrayList<>();
//这个list存放所有数组
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0 || target < 0) {
return lists;
}
List<Integer> list = new ArrayList<>();
dfs(list,candidates,target,0);
//第一个list存放小数组，
return lists;
}
private static void dfs(List<Integer> list, int[] candidates,int target,int start){
//递归的终止条件
if(target < 0){
return;
}
if(target == 0){
lists.add(new ArrayList<>(list));
}else {
for (int i=start;i<candidates.length;i++){
list.add(candidates[i]);
//*********************************************************
//因为每个数字都可以使用无数次，所以递归还可以从当前元素开始
//*********************************************************
dfs(list,candidates,target-candidates[i],i);
list.remove(list.size()-1);
}
}三数之和
题目
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：
跟两数之和不同的是，三数之后要输出的是不同三元组的集合。因此，我们考虑先将nums进行排序，将nums[i]作为第一个加数，从i+1到nums.length-1之间初始化两个指针left，right，为了避免有重复的情况，当nums[i]==nums[i-1],说明有重复的情况，开始下一个循环。如果num[i]+num[left]+num[right]>0,说明加多了，让right–，如果num[i]+num[left]+num[right]<0,说明加少了，让left++，如果等于0，说明符合条件，将这一组解加到集合中，这是也应该避免第二个加数和第三个加数重复的情况。
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] + nums[i] > 0) {
right--;
} else if (nums[left] + nums[right] + nums[i] < 0) {
left++;
} else {
list.add(Arrays.asList(nums[left], nums[right], nums[i]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return list;
}
京公网安备 11010502036488号