【***】两数和_三数和_最接近三数和

*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] ]

思路：

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

Follow-up 系列（面试高频）

Follow-up1：如果数组极大，全部数据在磁盘，内存放不下，怎么求三数之和？

核心难点：标准解法需要全数组排序，内存放不下，不能一次性 load 数组。思路：外部排序 + 多路归并得到有序文件，然后分片枚举 + 双指针

分片：大文件切分成多个小文件，每个分片读入内存，内部排序，写回磁盘；得到 N 个有序小文件。
多路归并，生成全局有序的大文件（磁盘）。现在数组整体有序，但仍然不能一次性全部加载内存。
枚举 i：依次读取每个候选a=nums[i]；
对每个固定 a，在 a后面的有序区间，使用外部双指针：
- left 从 i 后面位置，right 从文件末尾；
- 按需从磁盘读对应位置的数据，计算 sum；根据 sum 大小移动指针；

缺点：IO 开销巨大，工程上很少这么做。备选方案（哈希分片）：按数值哈希分成多个文件；遍历 a，需要找b + c = -a，b、c 落在对应分片；分片内做两数之和。面试口述要点：
内存放不下，不能直接 sort；必须外部排序；
外部排序后，有序大文件做双指针，但磁盘随机读性能很差；
工程场景，如果只需要存在性（是否有一组解），可以用哈希分片；如果要全部不重复三元组，代价极高。