java 寻找和为定值的多个数_算法笔记_037:寻找和为定值的两个数（Java）
1 問題描述
輸入一個整數數組和一個整數，在數組中查找兩個數，滿足他們的和正好是輸入的那個整數。如果有多對數的和等于輸入的整數，輸出任意一對即可。例如，如果輸入數組[1,2,4,5,7,11,15]和整數15，那么由于4+11 = 15，因此輸出4和11。
2 解決方案
2.1 排序夾逼法
首先將整數數組，使用合并排序進行從小打到的排序，然后對這個排完序的數組從兩頭往中間遍歷，一旦出現兩個數的和等于輸入的那個整數，則立即輸出這兩個數，并結束遍歷。
具體代碼如下：
package com.liuzhen.array_2;
public class TwoSumN {
/*
* 參數A：給定的一個從小到大排序的數組
* 參數n:待求和數n
* 函數功能：打印出A中兩個元素，滿足A[i]+A[j] = n
*/
public void getTwoSumN(int[] A,int n){
int start = 0;
int end = A.length - 1;
while(start < end){
if(A[start] + A[end] == n){
System.out.println("\n數組中元素A["+start+"]" +
" + A["+end+"] = "+n+",A["+start+"] = "+A[start]+",A["+end+"] = "+A[end]);
break;
}
else{
if(A[start] + A[end] > n)
end--;
else
start++;
}
}
}
//歸并排序
public void mergeSort(int[] A){
if(A.length > 1){
int[] leftA = getHalfArray(A,0); //數組A的左半部分
int[] rightA = getHalfArray(A,1); //數組A的右半部分
mergeSort(leftA);
mergeSort(rightA);
getMerge(A,leftA,rightA);
}
}
/*
* 參數A：要進行折半的數組
* 參數judge:judge == 0表示返回數組A左上半部分，judge != 0表示返回數組A的右半部分
* 函數功能：把數組按照長度均分為上半部分和下半部分
*/
public int[] getHalfArray(int[] A,int judge){
int[] result;
if(judge == 0){
result = new int[A.length/2];
for(int i = 0;i < A.length/2;i++)
result[i] = A[i];
}
else{
result = new int[A.length - A.length/2];
for(int i = 0;i < A.length - A.length/2;i++)
result[i] = A[i+A.length/2];
}
return result;
}
/*
*參數A：給定待排序數組
*參數leftA:數組A的左半部分
*參數rightA:數組的右半部分
*函數功能：返回數組A的從小到大排序
*/
public void getMerge(int[] A,int[] leftA,int[] rightA){
int i = 0; //用于計算當前遍歷leftA的元素個數
int j = 0; //用于計算當前遍歷rightA的元素個數
int count = 0; //用于計算當前得到按從小到大排序的A的元素個數
while(i < leftA.length && j < rightA.length){
if(leftA[i] < rightA[j]){
A[count++] = leftA[i];
i++;
}
else{
A[count++] = rightA[j];
j++;
}
}
if(i < leftA.length){
while(i < leftA.length)
A[count++] = leftA[i++];
}
if(j < rightA.length){
while(j < rightA.length)
A[count++] = rightA[j++];
}
}
public static void main(String[] args){
TwoSumN test = new TwoSumN();
int[] A = {2,1,7,4,6,1,2,4,3,6,8,4,2,1,7,3,4,6,8,3,4};
test.mergeSort(A);
System.out.println("對數組A進行合并排序后結果：");
for(int i = 0;i < A.length;i++)
System.out.print(A[i]+" ");
test.getTwoSumN(A, 10);
}
}
運行結果;
對數組A進行合并排序后結果：
1 1 1 2 2 2 3 3 3 4 4 4 4 4 6 6 6 7 7 8 8
數組中元素A[3] + A[20] = 10,A[3] = 2,A[20] = 8
算法筆記_041:尋找和為定值的多個數(Java)
目錄 1 問題描述 2 解決方案 1 問題描述 輸入兩個整數n和sum,要求從數列1,2,3,...,n中隨意取出幾個數,使得它們的和等于sum,請將其中所有可能的組合列出來. 2 解決方案 上述問題 ...
在數組中尋找和為定值的n個數
/*-------------------------------------------------------*/ /*尋找和為定值的兩個數 輸入一個數組A[0,N-1]和一個數字Sum,在數組中 ...
編程之法section II: 2.2 和為定值的兩個數
====數組篇==== 2.2 求和為定值的兩個數: 題目描述:有n個整數,找出其中滿足兩數相加為target的兩個數(如果有多組滿足,只需要找出其中一組),要求時間復雜度盡可能低. 解法一: 思路: ...
【Data Structure &; Algorithm】在排序數組中查找和為定值的兩個數
在排序數組中查找和為定值的兩個數 題目:輸入一個已經按升序排序過的數組和一個數字,在數組中查找兩個數,使得它們的和正好是輸入的那個數字,要求時間復雜度是O(n).如果有多對數字的和等于輸入的數字,輸出 ...
Java實現尋找和為定值的多個數
1 問題描述 輸入兩個整數n和sum,要求從數列1,2,3,-,n中隨意取出幾個數,使得它們的和等于sum,請將其中所有可能的組合列出來. 2 解決方案 上述問題是典型的背包問題的應用,即先找出n個數 ...
【劍指offer】和為定值的兩個數
轉載請注明出處:http://blog.csdn.net/ns_code/article/details/24933341 題目描寫敘述: 輸入一個遞增排序的數組和一個數字S,在數組中查找兩個數,是的 ...
【劍指offer學習】求和為定值的兩個數(拓展)
接著上面一篇文章:?http://blog.csdn.net/u013476464/article/details/40651451 接下來我們拓展一下題目,如果數組是亂序的,并且規定數組中的元素所有 ...
算法筆記_035:尋找最小的k個數(Java)
目錄 1 問題描述 2 解決方案 2.1 全部排序法 2.2 部分排序法 2.3 用堆代替數組法 2.4線性選擇算法 ? 1 問題描述 有n個整數,請找出其中最小的k個數,要求時間復雜度盡可能低. 2 ...
算法筆記_031:計算中值和選擇問題(Java)
目錄 1 問題描述? 2 解決方案 2.1 計算中值問題 2.2 選擇問題 ? 1 問題描述 中值問題是求一個n個數列表中某一數組下標k,它要求該下標元素比列表中的一半元素大,又比另一半元素小,這個中 ...
隨機推薦
ReactJS入門(四)—— 組件API
本篇將介紹 React 組件的API,其中主要的幾個API我們在第一篇的時候便已介紹過,這里可以做個溫故知新. 本篇的代碼你也可以在我的Github上獲取到. setState 參數:?nextSta ...
深入理解Bootstrap筆記
框架介紹 1.框架簡介 2.CSS基本語法 3.JavaScript基本語法 4.Bootstrap整體架構 5.12柵格系統 6.CSS組件架構設計思想 7.JavaScript插件架構 CSS布局 ...
iOS——Command-Line 查看當前SDK版本并修改默認SDK版本
在工作中可能會碰到用命令行編譯.打包iOS應用程序的情況(xcodebuild相關命令). 但是由于SDK版本問題,會報錯,說某SDK版本不對,可能是因為升級Xcode導致的SDK版本升級,為了避免高 ...
objective-c中字符串長度計算
我們知道,在c語言中,使用sizeof ()計算在內存中占用的字節數, 引用string.h后,使用strlen()計算字符串的長度(不包含\0). 而在object-c中, "length ...
Struts2 框架驗證
struts2框架驗證(xml方式):?? ?* 首先要從頁面中獲取對應的標簽name屬性的值,在動作類action中聲明同名的屬性,提供get和set方法?? ??? ?* 創建一個xml格式驗證文 ...
STM32串口usart發送數據
主函數請直接關注41行到47行代碼!! #include "stm32f10x.h" // 相當于51單片機中的 #include #include ...
新人入坑Redis必會的吐血總結
新人入坑Redis必會的吐血總結 一.什么是Redis Redis是一個使用C語言開發的開源的高性能的key-value存儲系統,我們可以把它近似理解為Java Map.簡單來講,Redis是一種NO ...
JDBC輔助類封裝 及應用
一:代碼圖解: 二:配置文件: driverClassName=com.mysql.jdbc.Driver url=jdbc\:mysql\://127.0.0.1\:3306/xlzj_sh_new ...
Ubuntu18.10下運行blender2.80bate閃退(問題?)
Ubuntu18.10下直接運行blender2.80bate閃退, 運行blender2.79正常. ================= root@tom-laptop:/# uname -aLin ...
禁用firefox 56自動更新
firefox 56支持舊式擴展,這很重要! 它卻自動更新,簡單地關了也不行,很是牛氓! ========== -備份C:\Users\用戶名\AppData\Roaming\Mozilla\Fire ...
總結
以上是生活随笔為你收集整理的java 寻找和为定值的多个数_算法笔记_037:寻找和为定值的两个数（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 信用卡呆账啥意思
- 下一篇： apple pay怎么绑定支付宝