帮我们公司做网站,郑州建站时间,wordpress nova,windows优化大师官方下载目录
一、查找总价格为目标值的两个商品
题目
题解
方法一#xff1a;暴力枚举
方法二#xff1a;对撞指针
二、两数之和
题目
题解
方法一#xff1a;暴力枚举
方法二#xff1a;哈希表法
三、三数之和
题目
题解
方法一#xff1a;排序暴力枚举set去重
…
目录
一、查找总价格为目标值的两个商品
题目
题解
方法一暴力枚举
方法二对撞指针
二、两数之和
题目
题解
方法一暴力枚举
方法二哈希表法
三、三数之和
题目
题解
方法一排序暴力枚举set去重
方法二排序双指针
四、四数之和
题目
题解
方法一排序暴力枚举set去重
方法二排序双指针
五、四数相加II
题目
题解
方法一暴力枚举
方法二两两合并 一、查找总价格为目标值的两个商品 题目 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。 示例 1
输入price [3, 9, 12, 15], target 18
输出[3,15] 或者 [15,3]示例 2
输入price [8, 21, 27, 34, 52, 66], target 61
输出[27,34] 或者 [34,27]提示
1 price.length 10^5
1 price[i] 10^6
1 target 2*10^6 题解
方法一暴力枚举
通过双层循环在数组中依次遍历查找两数之和为目标值target的数组元素需要注意i是从下标为0的位置开始循环j不能与i重复查询故j设置为从下标为1的位置开始循环此方法的时间复杂度为On^2。
class Solution {public int[] twoSum(int[] nums, int target) {int i 0,j 0,s[];for(i0;inums.length;i){for(ji1;jnums.length;j){if(nums[i]nums[j] target){return new int[]{i, j};}}}return new int[0];}
}
方法二对撞指针
本题是升序的数组因此可以用「对撞指针」优化时间复杂度。算法流程如下
初始化 left right 分别指向数组的左右两端不是我们理解的指针而是数组的下标当 left right 的时候一直循环 当 nums[left] nums[right] target 时说明找到结果记录结果并且返回 当 nums[left] nums[right] target 时对于 nums[left] 而言此时 nums[right] 相当于是 nums[left] 能碰到的最大值。如果此时不符合要求我们可以让left使和变大当 nums[left] nums[right] target 时同理我们可以舍去nums[right] 因为和过大了应该小一点。让 right-- 继续比较下一组数据而 left 指针不变
class Solution {public int[] twoSum(int[] nums, int target) {int i 0, j nums.length - 1;while(i j) {int s nums[i] nums[j];if(s target) i;else if(s target) j--;else return new int[] { nums[i], nums[j] };}return new int[0];}
} 二、两数之和 题目 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]提示
2 nums.length 104
-109 nums[i] 109
-109 target 109
只会存在一个有效答案 本题与第一题区别在于 1、数组不是升序的就不能使用对撞指针即使你排序后对应下标也不是原来的下标当然也可以哈希映射2、返回值要返回下标所以可以使用哈希映射 题解
方法一暴力枚举
此处省略。。。。
方法二哈希表法 科普一下什么是哈希表首先介绍一下哈希函数哈希函数是一种根据函数和查找关键字key直接确定出查找值所在位置的函数而哈希表则是基于哈希函数所建立的一种查找表它是由数组和链表组成的通过键值对的方式存取数据即【key,value】通过哈希函数它将key转换成对应的数组下标。 思考一下方法一的暴力枚举法的时间复杂度之所以高是因为代码中嵌套两层循环去遍历数组那么有没有什么方法只需要遍历一次数组就可以得到最终的结果呢分析可知按照暴力枚举的思路我们需要在数组中既找出num[i],又要找出num[j],然后才能判断两者之和是否等于target。
简化一下思维方式其实我们也可以只遍历一次数组得到每次数组下标为i处的元素的值然后判断数组中是否包含某个元素满足target-num[i]num[j]即可。
因此我们可以先创建一个哈希表对于每一个num[i],去判断哈希表中是否有元素的值等于target-num[i]然后将num[i]的值插入哈希表中这样就可以保证元素不会和自身匹配。搞清逻辑之后下面来看一下代码实现此时的时间复杂度为On。 package com.water.exec;import java.util.*;public class ArrayUtils {public static void main(String[] args) {test1();}public static void test1() {int[] arr {-1, 4, 6, 3, -1, 2, 0, 1};System.out.print(原始的arr是);print(arr);sort(arr);findTwo(arr, 4);}public static void sort(int[] arr) {for (int i 0; i arr.length; i) {for (int j i 1; j arr.length; j) {if (arr[i] arr[j]) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}}}System.out.print(排序之后的arr是);print(arr);}/** 两数之和* */public static void findTwo(int[] arr, int target){MapInteger, Integer map new HashMap();int[] res new int[2];for (int i 0; i arr.length; i) {int t target - arr[i];if(map.containsKey(t)){res[0] arr[i];res[1] t;break;}map.put(arr[i], i);}System.out.print(两数之和);print(res);}public static void print(int[] arr) {for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}
} 代码执行结果 三、三数之和 题目 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示
3 nums.length 3000
-105 nums[i] 105 题解
方法一排序暴力枚举set去重
时间复杂度是O(n^3)。
方法二排序双指针
找的过程沿用之前的双指针的思路因此本地可以认为是两数之和问题去重操作。
思路如下
数组排序固定一个数num[i]在该数后面的区间内利用“双指针算法快速找到两个的和等于 -num[i] 即可对于去重操作额外进行 代码如下
package com.water.exec;import java.util.*;public class ArrayUtils {public static void main(String[] args) {test1();}public static void test1() {int[] arr {-1, 4, 6, 3, -1, 2, 0, 1};System.out.print(原始的arr是);print(arr);sort(arr);findThree(arr);}public static void sort(int[] arr) {for (int i 0; i arr.length; i) {for (int j i 1; j arr.length; j) {if (arr[i] arr[j]) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}}}System.out.print(排序之后的arr是);print(arr);}/** 三数之和* */public static void findThree(int[] arr){int len arr.length;if(len 3 || arr null){ // 当前数组的长度为空或者长度小于3时直接退出return;}int mid_index 0; // 找到中间索引for (int i 0; i len; i) {if(arr[i] 0){mid_index i;break;}}ListListInteger res new ArrayList();for(int i 0; i mid_index; i){if(arr[i] 0){break;}if(i 0 arr[i] arr[i-1]){ //去重当起始的值等于前一个元素那么得到的结果将会和前一次相同continue;}int left i 1;int right len - 1;while(left right){int sum arr[i] arr[left] arr[right];if(sum 0){res.add(Arrays.asList(arr[i], arr[left], arr[right])); // 将三数的结果集加入到结果集中//在将左指针和右指针移动的时候先对左右指针的值进行判断//如果重复直接跳过。while (left right arr[left] arr[left1]){ //去重因为i不变当此时l取的数的值与前一个数相同所以不用重复计算left;}while (left right arr[right] arr[right-1]){ //去重因为i不变当此时r取的数的值与前一个相同所以不用重复计算right--;}left;right--;} else if (sum 0) { // 如果结果小于0说明当前l太小将左指针右移left;} else { // 如果结果大于0说明当前r太大将右指针左移right--;}}}System.out.println(三数之和 res.toString());}public static void print(int[] arr) {for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}
}
代码执行结果 四、四数之和
题目 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 示例 1
输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2
输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]]提示
1 nums.length 200
-109 nums[i] 109
-109 target 109 题解
方法一排序暴力枚举set去重
找到出四个数之和等于target即可但是下标不能相同且是不重复的四元组比如[-2,0,0,2]和[-2,2,0,0]是一样的所以也告诉我们需要去掉重复值的。
时间复杂度是O(n^4)一定会超时。
方法二排序双指针
找的过程沿用之前的双指针的思路因此本地可以认为是两数之和问题去重操作。
思路如下
首先先sort函数进行排序还是和三数之和的算法原理相似固定一个数a在a后面的区间内利用三数之和“算法思路找到三个数使这三个数的和等于target-a;依次固定一个数 b在b后面的区间内利用”双指针“算法快速找到2个数和为target-a-b对于去重操作额外进行 代码如下
package com.water.exec;import java.util.*;public class ArrayUtils {public static void main(String[] args) {test1();}public static void test1() {int[] arr {-1, 4, 6, 3, -1, 2, 0, 1};System.out.print(原始的arr是);print(arr);sort(arr);findThree(arr);findTwo(arr, 4);findFour(arr, 1);}public static void sort(int[] arr) {for (int i 0; i arr.length; i) {for (int j i 1; j arr.length; j) {if (arr[i] arr[j]) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}}}System.out.print(排序之后的arr是);print(arr);}/** 三数之和* */public static void findThree(int[] arr){int len arr.length;if(len 3 || arr null){ // 当前数组的长度为空或者长度小于3时直接退出return;}int mid_index 0; // 找到中间索引for (int i 0; i len; i) {if(arr[i] 0){mid_index i;break;}}ListListInteger res new ArrayList();for(int i 0; i mid_index; i){if(arr[i] 0){break;}if(i 0 arr[i] arr[i-1]){ //去重当起始的值等于前一个元素那么得到的结果将会和前一次相同continue;}int left i 1;int right len - 1;while(left right){int sum arr[i] arr[left] arr[right];if(sum 0){res.add(Arrays.asList(arr[i], arr[left], arr[right])); // 将三数的结果集加入到结果集中//在将左指针和右指针移动的时候先对左右指针的值进行判断//如果重复直接跳过。while (left right arr[left] arr[left1]) left; //去重因为i不变当此时l取的数的值与前一个数相同所以不用重复计算while (left right arr[right] arr[right-1]) right--; //去重因为i不变当此时r取的数的值与前一个相同所以不用重复计算left;right--;} else if (sum 0) { // 如果结果小于0说明当前l太小将左指针右移left;} else { // 如果结果大于0说明当前r太大将右指针左移right--;}}}System.out.println(三数之和 res.toString());}/** 两数之和* */public static void findTwo(int[] arr, int target){MapInteger, Integer map new HashMap();int[] res new int[2];for (int i 0; i arr.length; i) {int t target - arr[i];if(map.containsKey(t)){res[0] arr[i];res[1] t;break;}map.put(arr[i], i);}System.out.print(两数之和);print(res);}/** 四数之和* */public static void findFour(int[] arr, int target) {int length arr.length;if (arr null || length 4) return; // 当前数组的长度为空或者长度小于4时直接退出ListListInteger res new ArrayList();for (int i 0; i length - 3; i) {// 固定aif (i 0 arr[i] arr[i - 1]) continue; //去重当起始的值等于前一个元素那么得到的结果将会和前一次相同if ((long) arr[i] arr[i 1] arr[i 2] arr[i 3] target) break; // 早停if ((long) arr[i] arr[length - 3] arr[length - 2] arr[length - 1] target) continue; // 早停// 找target-afor (int j i 1; j length - 2; j) {// 固定bif (j i 1 arr[j] arr[j - 1]) continue; //去重当起始的值等于前一个元素那么得到的结果将会和前一次相同if ((long) arr[i] arr[j] arr[j 1] arr[j 2] target) break; // 早停if ((long) arr[i] arr[j] arr[length - 2] arr[length - 1] target) continue; // 早停// 找target-a-bint left j 1, right length - 1;while (left right) {long sum (long) arr[i] arr[j] arr[left] arr[right];if (sum target) {res.add(Arrays.asList(arr[i], arr[j], arr[left], arr[right])); // 将三数的结果集加入到结果集中while (left right arr[left] arr[left 1]) left; //去重因为i不变当此时l取的数的值与前一个数相同所以不用重复计算left;while (left right arr[right] arr[right - 1]) right--; //去重因为i不变当此时r取的数的值与前一个数相同所以不用重复计算right--;}else if (sum target) left; // 如果结果小于target说明当前l太小将左指针右移else right--; // 如果结果大于target说明当前r太大将右指针左移}}}System.out.println(四数之和 res.toString());}public static void print(int[] arr) {for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}
}
代码的执行结果 五、四数相加II
题目 给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足 0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0 示例 1
输入nums1 [1,2], nums2 [-2,-1], nums3 [-1,2], nums4 [0,2]
输出2
解释
两个元组如下
1. (0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0
2. (1, 1, 0, 0) - nums1[1] nums2[1] nums3[0] nums4[0] 2 (-1) (-1) 0 0示例 2
输入nums1 [0], nums2 [0], nums3 [0], nums4 [0]
输出1提示
n nums1.length
n nums2.length
n nums3.length
n nums4.length
1 n 200
-228 nums1[i], nums2[i], nums3[i], nums4[i] 228 题解
方法一暴力枚举 对于这道题我们的第一思路就是暴力枚举我们可以写一个四层的for循环进行暴力匹配只要相加的结果等于0就进行统计。但是我们会发现我们的事件复杂度为O(N^4)事件复杂度非常大所以如果使用这个思路进行问题的解决一定会超时所以我们采用其他思路进行题目的解答操作。 方法二两两合并
在官方题解当中我们可以学到一个解法我们可以将四个数组分成为两个一组的形式将一组当中的两个数组进行相加合并将两个数组当中的元素进行完全匹配相加合并之后就可以将两组新的数据进行匹配之后就可以将题目的要求修改为两个数组查找指定的值。需要注意的是我们同样需要使用哈希表进行数据的处理以提高代码的运行速率。
本题是四个独立的数组只要找到A[i] B[j] C[k] D[l] 0就可以不用考虑有重复的四个元素相加等于0的情况即不用去重。
解题步骤
定义一个unordered_mapkey放a和b两数之和value 放a和b两数之和出现的次数。遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。定义int变量count用来统计 abcd 0 出现的次数。在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了。。
我们会发现这种算法的时间复杂度为O(N^2)其主要需要进行的操作就是数组的合并以及之后的数据查找操作。根据上述思路所编写的代码如下所示
package com.water.exec;import java.util.*;public class ArrayUtils {public static void test4(){fourSumCount(new int[]{1, 2}, new int[]{-2, -1}, new int[]{-1, 2}, new int[]{0, 2});}/** 四数相加II* */public static void fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {MapInteger, Integer map new HashMap();int count 0;for (int a : nums1){for (int b : nums2){int sum a b;//getOrDefault的第一个参数是key第二个参数是自己设置的默认值0如果key存在则返回其出现次数key不存在则返回0map.put(sum, map.getOrDefault(sum, 0) 1);}}for (int c : nums3){for (int d : nums4){count map.getOrDefault(0 - c - d, 0);}}System.out.println(四数相加II count);}
}
代码的执行结果
