开发者管理/资源优化排名网站

目录

一、查找总价格为目标值的两个商品

题目

题解

方法一：暴力枚举

方法二：对撞指针

二、两数之和 

题目

题解

方法一：暴力枚举

方法二：哈希表法

三、三数之和

题目

题解

方法一：排序+暴力枚举+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的位置开始循环，此方法的时间复杂度为O（n^2）。

class Solution {public int[] twoSum(int[] nums, int target) {int i = 0,j = 0,s[];for(i=0;i<nums.length;i++){for(j=i+1;j<nums.length;j++){if(nums[i]+nums[j] == target){return new int[]{i, j};}}}return new int[0];}
}

方法二：对撞指针

本题是升序的数组，因此可以用「对撞指针」优化时间复杂度。算法流程如下：

1. 初始化 left ，right 分别指向数组的左右两端（不是我们理解的指针，而是数组的下标）；
2. 当 left < right 的时候，一直循环
   1.  当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；
   2.  当 nums[left] + nums[right] < target 时，对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的最大值。如果此时不符合要求，我们可以让left++，使和变大
   3. 当 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]的值插入哈希表中，这样就可以保证元素不会和自身匹配。搞清逻辑之后，下面来看一下代码实现，此时的时间复杂度为：O（n）。

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){Map<Integer, 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)。

方法二：排序+双指针

找的过程沿用之前的双指针的思路，因此本地可以认为是两数之和问题+去重操作。

思路如下：

1. 数组排序
2. 固定一个数num[i]
3. 在该数后面的区间内，利用“双指针算法快速找到两个的和等于 -num[i] 即可
4. 对于去重操作，额外进行

代码如下，

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;}}List<List<Integer>> 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[left+1]){  //去重，因为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 < n
• a、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)，一定会超时。

方法二：排序+双指针

找的过程沿用之前的双指针的思路，因此本地可以认为是两数之和问题+去重操作。

思路如下：

1. 首先先sort函数进行排序
2. 还是和三数之和的算法原理相似，固定一个数a
3. 在a后面的区间内，利用"三数之和“算法思路找到三个数，使这三个数的和等于target-a;
4. 依次固定一个数 b
5. 在b后面的区间内，利用”双指针“算法，快速找到2个数和为target-a-b
6. 对于去重操作，额外进行

代码如下：

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;}}List<List<Integer>> 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[left+1]) 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){Map<Integer, 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时，直接退出List<List<Integer>> 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 < n
• nums1[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的情况，即不用去重。

解题步骤：

1. 定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5. 最后返回统计值 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) {Map<Integer, 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);}
}

代码的执行结果：