*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()的值和ipublic int[] twoSum(int[] nums,int target){ MapInteger,Integer mapnew HashMap(); for(int i0;inums.length;i){ int complementtarget-nums[i]; if(map.containsKey(complement)){ System.out.println(map.get(complement)\ti); return new int[]{map.get(complement),i}; } map.put(nums[i], i); } throw new IllegalArgumentException(no two sum solution); }*15三数之和给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。示例给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为[[-1, 0, 1],[-1, -1, 2]]思路总体思路排序双指针 nlogn n^21.对数组排序2.固定指针i,分别加左右两个指针从数组中生下的左右两头开始往中间查找。-4 -1 -1 0 1 2 i l rnum[i]0 结束num[i]num[i-1]跳过重复的inum[L]num[L1]重复跳过Lnum[R]num[R-1]重复R--class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); if(numsnull || nums.length3){ return res; } Arrays.sort(nums);//排序 for(int i0;inums.length;i){ if(i0 nums[i]nums[i-1]) continue;//去重 int lefti1; int rightnums.length-1; while(leftright){ int sumnums[i]nums[left]nums[right]; if(sum0){ res.add(Arrays.asList(nums[i],nums[left],nums[right]));//满足 while(leftright nums[left]nums[left1]){//注意边界判断 left;//去重 } while(rightleft nums[right]nums[right-1]){ right--;//去重 } left; right--; }else if(sum0){ left; }else{ right --; } } } return res; } }*16最近接的三数之和给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如给定数组 nums [-121-4], 和 target 1.与 target 最接近的三个数的和为 2. (-1 2 1 2).思路同三数之和为0相同排序双指针public int threeSumClosest(int[] nums, int target) { if(numsnull || nums.length3){ return -1; } Arrays.sort(nums); int resnums[0]nums[1]nums[2]; for(int i0;inums.length;i){ int lefti1; int rightnums.length-1; while(leftright){ int sumnums[i]nums[left]nums[right]; if(Math.abs(target-res)Math.abs(target-sum)){ ressum; } if(sumtarget){//三数之和目标 left右移动 left; }else if(sumtarget){ right--; }else{ return sum; } } } return res; }18.四数之和给定一个包含n个整数的数组nums和一个目标值target判断nums中是否存在四个元素abc和d使得abcd的值与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依次读取每个候选anums[i]对每个固定 a在 a后面的有序区间使用外部双指针left 从 i 后面位置right 从文件末尾按需从磁盘读对应位置的数据计算 sum根据 sum 大小移动指针缺点IO 开销巨大工程上很少这么做。 备选方案哈希分片 按数值哈希分成多个文件遍历 a需要找b c -ab、c 落在对应分片分片内做两数之和。 面试口述要点内存放不下不能直接 sort必须外部排序外部排序后有序大文件做双指针但磁盘随机读性能很差工程场景如果只需要存在性是否有一组解可以用哈希分片如果要全部不重复三元组代价极高。Follow-up2能不能不用排序哈希表解法可以。外层遍历 a内层两数之和哈希但是很难去重需要把三元组排序存入 set 去重空间开销大面试优先推荐排序双指针。。
【***】两数和_三数和_最接近三数和_四数和
*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()的值和ipublic int[] twoSum(int[] nums,int target){ MapInteger,Integer mapnew HashMap(); for(int i0;inums.length;i){ int complementtarget-nums[i]; if(map.containsKey(complement)){ System.out.println(map.get(complement)\ti); return new int[]{map.get(complement),i}; } map.put(nums[i], i); } throw new IllegalArgumentException(no two sum solution); }*15三数之和给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。示例给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为[[-1, 0, 1],[-1, -1, 2]]思路总体思路排序双指针 nlogn n^21.对数组排序2.固定指针i,分别加左右两个指针从数组中生下的左右两头开始往中间查找。-4 -1 -1 0 1 2 i l rnum[i]0 结束num[i]num[i-1]跳过重复的inum[L]num[L1]重复跳过Lnum[R]num[R-1]重复R--class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); if(numsnull || nums.length3){ return res; } Arrays.sort(nums);//排序 for(int i0;inums.length;i){ if(i0 nums[i]nums[i-1]) continue;//去重 int lefti1; int rightnums.length-1; while(leftright){ int sumnums[i]nums[left]nums[right]; if(sum0){ res.add(Arrays.asList(nums[i],nums[left],nums[right]));//满足 while(leftright nums[left]nums[left1]){//注意边界判断 left;//去重 } while(rightleft nums[right]nums[right-1]){ right--;//去重 } left; right--; }else if(sum0){ left; }else{ right --; } } } return res; } }*16最近接的三数之和给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如给定数组 nums [-121-4], 和 target 1.与 target 最接近的三个数的和为 2. (-1 2 1 2).思路同三数之和为0相同排序双指针public int threeSumClosest(int[] nums, int target) { if(numsnull || nums.length3){ return -1; } Arrays.sort(nums); int resnums[0]nums[1]nums[2]; for(int i0;inums.length;i){ int lefti1; int rightnums.length-1; while(leftright){ int sumnums[i]nums[left]nums[right]; if(Math.abs(target-res)Math.abs(target-sum)){ ressum; } if(sumtarget){//三数之和目标 left右移动 left; }else if(sumtarget){ right--; }else{ return sum; } } } return res; }18.四数之和给定一个包含n个整数的数组nums和一个目标值target判断nums中是否存在四个元素abc和d使得abcd的值与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依次读取每个候选anums[i]对每个固定 a在 a后面的有序区间使用外部双指针left 从 i 后面位置right 从文件末尾按需从磁盘读对应位置的数据计算 sum根据 sum 大小移动指针缺点IO 开销巨大工程上很少这么做。 备选方案哈希分片 按数值哈希分成多个文件遍历 a需要找b c -ab、c 落在对应分片分片内做两数之和。 面试口述要点内存放不下不能直接 sort必须外部排序外部排序后有序大文件做双指针但磁盘随机读性能很差工程场景如果只需要存在性是否有一组解可以用哈希分片如果要全部不重复三元组代价极高。Follow-up2能不能不用排序哈希表解法可以。外层遍历 a内层两数之和哈希但是很难去重需要把三元组排序存入 set 去重空间开销大面试优先推荐排序双指针。。
