目錄

一、查找總價(jià)格為目標(biāo)值的兩個(gè)商品

題目

題解

方法一：暴力枚舉

方法二：對(duì)撞指針

二、兩數(shù)之和?

題目

題解

方法一：暴力枚舉

方法二：哈希表法

三、三數(shù)之和

題目

題解

方法一：排序+暴力枚舉+set去重

方法二：排序+雙指針

四、四數(shù)之和

?題目

題解

方法一：排序+暴力枚舉+set去重

方法二：排序+雙指針

五、四數(shù)相加II

題目

題解

方法一：暴力枚舉

方法二：兩兩合并

一、查找總價(jià)格為目標(biāo)值的兩個(gè)商品

題目

購物車內(nèi)的商品價(jià)格按照升序記錄于數(shù)組 price。請(qǐng)?jiān)谫徫镘囍姓业絻蓚€(gè)商品的價(jià)格總和剛好是 target。若存在多種情況，返回任一結(jié)果即可。

示例 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

題解

方法一：暴力枚舉

通過雙層循環(huán)，在數(shù)組中依次遍歷查找兩數(shù)之和為目標(biāo)值target的數(shù)組元素，需要注意i是從下標(biāo)為0的位置開始循環(huán)，j不能與i重復(fù)查詢，故j設(shè)置為從下標(biāo)為1的位置開始循環(huán)，此方法的時(shí)間復(fù)雜度為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];}
}

方法二：對(duì)撞指針

本題是升序的數(shù)組，因此可以用「對(duì)撞指針」優(yōu)化時(shí)間復(fù)雜度。算法流程如下：

1. 初始化 left ，right 分別指向數(shù)組的左右兩端（不是我們理解的指針，而是數(shù)組的下標(biāo)）；
2. 當(dāng) left < right 的時(shí)候，一直循環(huán)
   1. ?當(dāng) nums[left] + nums[right] == target 時(shí)，說明找到結(jié)果，記錄結(jié)果，并且返回；
   2. ?當(dāng) nums[left] + nums[right] < target 時(shí)，對(duì)于 nums[left] 而言，此時(shí) nums[right] 相當(dāng)于是 nums[left] 能碰到的最大值。如果此時(shí)不符合要求，我們可以讓left++，使和變大
   3. 當(dāng) nums[left] + nums[right] > target 時(shí)，同理我們可以舍去nums[right] （因?yàn)楹瓦^大了，應(yīng)該小一點(diǎn)）。讓 right-- ，繼續(xù)比較下一組數(shù)據(jù)，而 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];}
}

二、兩數(shù)之和?

題目

給定一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)目標(biāo)值?target，請(qǐng)你在該數(shù)組中找出?和為目標(biāo)值?target? 的那?兩個(gè)?整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。

你可以按任意順序返回答案。

示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?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
只會(huì)存在一個(gè)有效答案

本題與第一題區(qū)別在于：

• 1、數(shù)組不是升序的，就不能使用對(duì)撞指針，即使你排序后，對(duì)應(yīng)下標(biāo)也不是原來的下標(biāo)，當(dāng)然也可以哈希映射
• 2、返回值要返回下標(biāo)，所以可以使用哈希映射?

題解

方法一：暴力枚舉

此處省略。。。。

方法二：哈希表法

科普一下什么是哈希表，首先介紹一下哈希函數(shù)，哈希函數(shù)是一種根據(jù)函數(shù)和查找關(guān)鍵字key，直接確定出查找值所在位置的函數(shù)，而哈希表則是基于哈希函數(shù)所建立的一種查找表，它是由數(shù)組和鏈表組成的，通過鍵值對(duì)的方式存取數(shù)據(jù)，即【key,value】，通過哈希函數(shù)，它將key轉(zhuǎn)換成對(duì)應(yīng)的數(shù)組下標(biāo)。

?

思考一下，方法一的暴力枚舉法的時(shí)間復(fù)雜度之所以高，是因?yàn)榇a中嵌套兩層循環(huán)去遍歷數(shù)組，那么有沒有什么方法只需要遍歷一次數(shù)組就可以得到最終的結(jié)果呢？分析可知，按照暴力枚舉的思路，我們需要在數(shù)組中既找出num[i],又要找出num[j],然后才能判斷兩者之和是否等于target。

簡(jiǎn)化一下思維方式，其實(shí)我們也可以只遍歷一次數(shù)組，得到每次數(shù)組下標(biāo)為i處的元素的值，然后判斷數(shù)組中是否包含某個(gè)元素滿足：target-num[i]==num[j]即可。

因此，我們可以先創(chuàng)建一個(gè)哈希表，對(duì)于每一個(gè)num[i],去判斷哈希表中是否有元素的值等于target-num[i]，然后將num[i]的值插入哈希表中，這樣就可以保證元素不會(huì)和自身匹配。搞清邏輯之后，下面來看一下代碼實(shí)現(xiàn)，此時(shí)的時(shí)間復(fù)雜度為：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);}/** 兩數(shù)之和* */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("兩數(shù)之和：");print(res);}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}

代碼執(zhí)行結(jié)果：

三、三數(shù)之和

題目

給你一個(gè)整數(shù)數(shù)組?nums?，判斷是否存在三元組?[nums[i], nums[j], nums[k]]?滿足?i != j、i != k?且?j != k?，同時(shí)還滿足?nums[i] + nums[j] + nums[k] == 0?。請(qǐng)

你返回所有和為?0?且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。示例 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去重

時(shí)間復(fù)雜度是O(n^3)。

方法二：排序+雙指針

找的過程沿用之前的雙指針的思路，因此本地可以認(rèn)為是兩數(shù)之和問題+去重操作。

思路如下：

1. 數(shù)組排序
2. 固定一個(gè)數(shù)num[i]
3. 在該數(shù)后面的區(qū)間內(nèi)，利用“雙指針?biāo)惴焖僬业絻蓚€(gè)的和等于 -num[i] 即可
4. 對(duì)于去重操作，額外進(jì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);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);}/** 三數(shù)之和* */public static void findThree(int[] arr){int len = arr.length;if(len < 3 || arr == null){  // 當(dāng)前數(shù)組的長(zhǎng)度為空，或者長(zhǎng)度小于3時(shí)，直接退出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]){  //去重，當(dāng)起始的值等于前一個(gè)元素，那么得到的結(jié)果將會(huì)和前一次相同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])); // 將三數(shù)的結(jié)果集加入到結(jié)果集中//在將左指針和右指針移動(dòng)的時(shí)候，先對(duì)左右指針的值，進(jìn)行判斷//如果重復(fù)，直接跳過。while (left < right && arr[left] == arr[left+1]){  //去重，因?yàn)閕不變，當(dāng)此時(shí)l取的數(shù)的值與前一個(gè)數(shù)相同，所以不用重復(fù)計(jì)算left++;}while (left < right && arr[right] == arr[right-1]){  //去重，因?yàn)閕不變，當(dāng)此時(shí)r取的數(shù)的值與前一個(gè)相同，所以不用重復(fù)計(jì)算right--;}left++;right--;} else if (sum < 0) { // 如果結(jié)果小于0，說明當(dāng)前l(fā)太小，將左指針右移left++;} else {  // 如果結(jié)果大于0，說明當(dāng)前r太大，將右指針左移right--;}}}System.out.println("三數(shù)之和：" + res.toString());}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}

代碼執(zhí)行結(jié)果：?

四、四數(shù)之和

?題目

給你一個(gè)由?n?個(gè)整數(shù)組成的數(shù)組?nums?，和一個(gè)目標(biāo)值?target?。請(qǐng)你找出并返回滿足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：

• 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去重

找到出四個(gè)數(shù)之和等于target即可，但是下標(biāo)不能相同，且是不重復(fù)的四元組，比如[-2,0,0,2]和[-2,2,0,0]是一樣的，所以也告訴我們需要去掉重復(fù)值的。

時(shí)間復(fù)雜度是O(n^4)，一定會(huì)超時(shí)。

方法二：排序+雙指針

找的過程沿用之前的雙指針的思路，因此本地可以認(rèn)為是兩數(shù)之和問題+去重操作。

思路如下：

1. 首先先sort函數(shù)進(jìn)行排序
2. 還是和三數(shù)之和的算法原理相似，固定一個(gè)數(shù)a
3. 在a后面的區(qū)間內(nèi)，利用"三數(shù)之和“算法思路找到三個(gè)數(shù)，使這三個(gè)數(shù)的和等于target-a;
4. 依次固定一個(gè)數(shù) b
5. 在b后面的區(qū)間內(nèi)，利用”雙指針“算法，快速找到2個(gè)數(shù)和為target-a-b
6. 對(duì)于去重操作，額外進(jì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);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);}/** 三數(shù)之和* */public static void findThree(int[] arr){int len = arr.length;if(len < 3 || arr == null){  // 當(dāng)前數(shù)組的長(zhǎng)度為空，或者長(zhǎng)度小于3時(shí)，直接退出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]){  //去重，當(dāng)起始的值等于前一個(gè)元素，那么得到的結(jié)果將會(huì)和前一次相同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])); // 將三數(shù)的結(jié)果集加入到結(jié)果集中//在將左指針和右指針移動(dòng)的時(shí)候，先對(duì)左右指針的值，進(jìn)行判斷//如果重復(fù)，直接跳過。while (left < right && arr[left] == arr[left+1]) left++; //去重，因?yàn)閕不變，當(dāng)此時(shí)l取的數(shù)的值與前一個(gè)數(shù)相同，所以不用重復(fù)計(jì)算while (left < right && arr[right] == arr[right-1]) right--; //去重，因?yàn)閕不變，當(dāng)此時(shí)r取的數(shù)的值與前一個(gè)相同，所以不用重復(fù)計(jì)算left++;right--;} else if (sum < 0) { // 如果結(jié)果小于0，說明當(dāng)前l(fā)太小，將左指針右移left++;} else {  // 如果結(jié)果大于0，說明當(dāng)前r太大，將右指針左移right--;}}}System.out.println("三數(shù)之和：" + res.toString());}/** 兩數(shù)之和* */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("兩數(shù)之和：");print(res);}/** 四數(shù)之和* */public static void findFour(int[] arr, int target) {int length = arr.length;if (arr == null || length < 4) return;  // 當(dāng)前數(shù)組的長(zhǎng)度為空，或者長(zhǎng)度小于4時(shí)，直接退出List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < length - 3; i++) {// 固定aif (i > 0 && arr[i] == arr[i - 1]) continue; //去重，當(dāng)起始的值等于前一個(gè)元素，那么得到的結(jié)果將會(huì)和前一次相同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; //去重，當(dāng)起始的值等于前一個(gè)元素，那么得到的結(jié)果將會(huì)和前一次相同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])); // 將三數(shù)的結(jié)果集加入到結(jié)果集中while (left < right && arr[left] == arr[left + 1]) left++; //去重，因?yàn)閕不變，當(dāng)此時(shí)l取的數(shù)的值與前一個(gè)數(shù)相同，所以不用重復(fù)計(jì)算left++;while (left < right && arr[right] == arr[right - 1]) right--; //去重，因?yàn)閕不變，當(dāng)此時(shí)r取的數(shù)的值與前一個(gè)數(shù)相同，所以不用重復(fù)計(jì)算right--;}else if (sum < target) left++; // 如果結(jié)果小于target，說明當(dāng)前l(fā)太小，將左指針右移else right--; // 如果結(jié)果大于target，說明當(dāng)前r太大，將右指針左移}}}System.out.println("四數(shù)之和：" + res.toString());}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}

代碼的執(zhí)行結(jié)果：

五、四數(shù)相加II

題目

給你四個(gè)整數(shù)數(shù)組?nums1、nums2、nums3?和?nums4?，數(shù)組長(zhǎng)度都是?n?，請(qǐng)你計(jì)算有多少個(gè)元組?(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
解釋：
兩個(gè)元組如下：
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

題解

方法一：暴力枚舉

?對(duì)于這道題，我們的第一思路就是暴力枚舉，我們可以寫一個(gè)四層的for循環(huán)進(jìn)行暴力匹配，只要相加的結(jié)果等于0就進(jìn)行統(tǒng)計(jì)。但是我們會(huì)發(fā)現(xiàn)，我們的事件復(fù)雜度為O(N^4)事件復(fù)雜度非常大，所以如果使用這個(gè)思路進(jìn)行問題的解決一定會(huì)超時(shí)，所以我們采用其他思路進(jìn)行題目的解答操作。

方法二：兩兩合并

在官方題解當(dāng)中我們可以學(xué)到一個(gè)解法：我們可以將四個(gè)數(shù)組分成為兩個(gè)一組的形式，將一組當(dāng)中的兩個(gè)數(shù)組進(jìn)行相加合并，將兩個(gè)數(shù)組當(dāng)中的元素進(jìn)行完全匹配相加，合并之后就可以將兩組新的數(shù)據(jù)進(jìn)行匹配，之后就可以將題目的要求修改為兩個(gè)數(shù)組查找指定的值。需要注意的是：我們同樣需要使用哈希表進(jìn)行數(shù)據(jù)的處理，以提高代碼的運(yùn)行速率。

本題是四個(gè)獨(dú)立的數(shù)組，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考慮有重復(fù)的四個(gè)元素相加等于0的情況，即不用去重。

解題步驟：

1. 定義一個(gè)unordered_map，key放a和b兩數(shù)之和，value 放a和b兩數(shù)之和出現(xiàn)的次數(shù)。
2. 遍歷大A和大B數(shù)組，統(tǒng)計(jì)兩個(gè)數(shù)組元素之和，和出現(xiàn)的次數(shù)，放到map中。
3. 定義int變量count，用來統(tǒng)計(jì) a+b+c+d = 0 出現(xiàn)的次數(shù)。
4. 在遍歷大C和大D數(shù)組，找到如果 0-(c+d) 在map中出現(xiàn)過的話，就用count把map中key對(duì)應(yīng)的value也就是出現(xiàn)次數(shù)統(tǒng)計(jì)出來。
5. 最后返回統(tǒng)計(jì)值 count 就可以了。。

我們會(huì)發(fā)現(xiàn)這種算法的時(shí)間復(fù)雜度為O(N^2)，其主要需要進(jìn)行的操作就是數(shù)組的合并，以及之后的數(shù)據(jù)查找操作。根據(jù)上述思路所編寫的代碼如下所示：

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});}/** 四數(shù)相加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的第一個(gè)參數(shù)是key，第二個(gè)參數(shù)是自己設(shè)置的默認(rèn)值（0），如果key存在則返回其出現(xiàn)次數(shù)，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("四數(shù)相加II：" + count);}
}

代碼的執(zhí)行結(jié)果：