*1两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

返回相加和为target的两个数下标

思路：

如果调用两层for循环也是可以的，但是时间复杂度大，所以可以借助map来执行复杂度为O(n)

对于输入数组nums中的每一个元素,检查target-nums[i]是否在map中，如果没有把<nums[i],i>值和下标加入map中，

如果存在，两个加数的下标就为map.get()的值和i

public int[] twoSum(int[] nums,int target){ Map<Integer,Integer> map=new HashMap(); for(int i=0;i<nums.length;i++){ int complement=target-nums[i]; if(map.containsKey(complement)){ System.out.println(map.get(complement)+"\t"+i); return new int[]{map.get(complement),i}; } map.put(nums[i], i); } throw new IllegalArgumentException("no two sum solution"); }

 

*15三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [   [-1, 0, 1],   [-1, -1, 2] ]

思路：

总体思路：排序+双指针  （nlogn + n^2）

1.对数组排序

2.固定指针i,分别加左右两个指针从数组中生下的左右两头开始往中间查找。

-4 -1 -1 0 1 2 i l r

num[i]>0 ：结束

num[i]=num[i-1]：跳过，重复的，i++

num[L]=num[L+1]：重复，跳过L++

num[R]=num[R-1]：重复，R--

 

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList(); if(nums==null || nums.length<3){ return res; } Arrays.sort(nums);//排序 for(int i=0;i<nums.length;i++){ if(i>0 && nums[i]==nums[i-1]) continue;//去重 int left=i+1; int right=nums.length-1; while(left<right){ int sum=nums[i]+nums[left]+nums[right]; if(sum==0){ res.add(Arrays.asList(nums[i],nums[left],nums[right]));//满足 while(left<right && nums[left]==nums[left+1]){//注意边界判断 left++;//去重 } while(right>left && nums[right]==nums[right-1]){ right--;//去重 } left++; right--; }else if(sum<0){ left++; }else{ right --; } } } return res; } }

*16最近接的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

思路：

同三数之和为0相同，排序+双指针

public int threeSumClosest(int[] nums, int target) { if(nums==null || nums.length<3){ return -1; } Arrays.sort(nums); int res=nums[0]+nums[1]+nums[2]; for(int i=0;i<nums.length;i++){ int left=i+1; int right=nums.length-1; while(left<right){ int sum=nums[i]+nums[left]+nums[right]; if(Math.abs(target-res)>Math.abs(target-sum)){ res=sum; } if(sum<target){//三数之和<目标 left右移动 left++; }else if(sum>target){ right--; }else{ return sum; } } } return res; }

18.四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路：

排序循环固定一个数同三个数相同